网站建设网站需要什么,福州百度推广优化排名,查看网站是否做百度推广,wordpress模板响应式AGC038D - Unique Path
Solution
此题较水。 大概就是简单路径唯一意味着连成一棵树#xff0c;因此先给这些限制的端点放在同一个连通块内#xff0c;然后如果有多条路径的限制的两端点在同一个连通块内#xff0c;则无解。
然后考虑如果没有多条路径的限制#xff0c;…AGC038D - Unique Path
Solution
此题较水。 大概就是简单路径唯一意味着连成一棵树因此先给这些限制的端点放在同一个连通块内然后如果有多条路径的限制的两端点在同一个连通块内则无解。
然后考虑如果没有多条路径的限制则还要连的边数最少为t−1t-1t−1最多为t(t−1)2\frac{t(t-1)}{2}2t(t−1)ttt为连通块个数直接判断即可。
如果有多条路径则还要连的边数最少为ttt一种可行方案是每个限制以以每个连通块的根为端点连成环最多为t(t−1)2\frac{t(t-1)}{2}2t(t−1)且连通块个数至少要有两个否则没法连成环。
时间复杂度O(nlgn)O(nlgn)O(nlgn)。
Code
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN600005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline ll read()
{ll f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
int f[MAXN];
struct Enode{ int u,v,c; } E[MAXN];
int find(int x) { return f[x]x?f[x]:f[x]find(f[x]); }
signed main()
{ll nread(),mread(),qread(),es0,ec0;for (int i1;in;i) f[i]i;for (int i1;iq;i){int uread()1,vread()1,cread();E[i](Enode){u,v,c};if (!cfind(u)!find(v)) f[find(u)]find(v),es;else if (c) ec;}for (int i1;iq;i) if (E[i].cfind(E[i].u)find(E[i].v)) { puts(No); return 0; }ll t0;for (int i1;in;i) if (find(i)i) t;if (ec) puts((m-estm-est*(t-1)/2t2)?Yes:No);else puts((m-est-1m-est*(t-1)/2)?Yes:No);return 0;
}
