S+二分图与网络流初步 A. 生成二分图 找出所有的二分图， 对于每个二分图自己，所有的连接方案肯定是两种颜色的乘积的两倍， 而单个二分图中每个点都可以与其他二分图的点相连，因为会重复计算，所以不用乘二。 最后因为 (u,v) 等价于 (v,u)， 所以把所有合法的边数除以 2 再减去已经有了的边数 m 就能得到答案。 代码： #include using namespace std; #define int long long const int N=2e5+5; int n,m,ans,y=1; int col[N],cnt[3]; vector g[N]; void dfs(int u,int c){ col[u]=c,cnt[c]++; for(int i=0;i>n>>m; for(int i=1;i>u>>v; g[u].push_back(v); g[v].push_back(u); } for(int i=1;i `#include using namespace std; #define int long long const int N=2e5+5; int n,m,ans,y=1; int col[N],cnt[3]; vectorint> g[N]; void dfs(int u,int c){ col[u]=c,cnt[c]++; for(int i=0;ig[u].size();i++){ int v=g[u][i]; if(col[v]==c) y=0; if(col[v]) continue; dfs(v,3-c); } } signed main(){ cin>>n>>m; for(int i=1;i int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } for(int i=1;i if(!col[i]){ cnt[1]=cnt[2]=0; dfs(i,1); ans+=cnt[1]*cnt[2]*2+(cnt[1]+cnt[2])*(n-cnt[1]-cnt[2]); } } if(!y) cout0; else cout2-m; return 0; }` C++ B. 图上同色最远 可以贪心想到，在“简单路径”上， 相邻的点最好不能染同样的颜色， 而题意正是使简单路径的最小值最大， 所以可以二分出 X， 代码： #include using namespace std; #define int long long const int N=2e6+5; struct node{ int v,w; }; int n,m; int col[N],w1[N],w2[N]; vector g[N]; void findw(int u,int w){ if(w=w1[u]) w2[u]=w; } bool dfs(int u,int x,int c){ col[u]=c; for(int i=0;i=x) continue; if(col[v]==col[u]) return 0; if(!col[v]&&!dfs(v,x,3-c)) return 0; } return 1; } bool check(int x){ memset(col,0,sizeof col); for(int i=1;i>n>>m; for(int i=1;i>u>>v>>w; g[u].push_back({v,w}); g[v].push_back({u,w}); findw(u,w),findw(v,w); } int l=0,r=LONG_LONG_MAX,ans; for(int i=1;i>1; if(check(mid)){ l=mid+1; ans=mid; } else r=mid-1; } cout `#include using namespace std; #define int long long const int N=2e6+5; struct node{ int v,w; }; int n,m; int col[N],w1[N],w2[N]; vector g[N]; void findw(int u,int w){ if(ww1[u]) w2[u]=w1[u],w1[u]=w; else if(ww2[u]&&w>=w1[u]) w2[u]=w; } bool dfs(int u,int x,int c){ col[u]=c; for(int i=0;ig[u].size();i++){ int v=g[u][i].v,w=g[u][i].w; if(w>=x) continue; if(col[v]==col[u]) return 0; if(!col[v]&&!dfs(v,x,3-c)) return 0; } return 1; } bool check(int x){ memset(col,0,sizeof col); for(int i=1;iif(!col[i]){ if(!dfs(i,x,1)) return 0; } return 1; } signed main(){ memset(w1,0x3f,sizeof w1); memset(w2,0x3f,sizeof w2); cin>>n>>m; for(int i=1;i int u,v,w; cin>>u>>v>>w; g[u].push_back({v,w}); g[v].push_back({u,w}); findw(u,w),findw(v,w); } int l=0,r=LONG_LONG_MAX,ans; for(int i=1;imin(r,w1[i]+w2[i]); while(l int mid=(l+r)>>1; if(check(mid)){ l=mid+1; ans=mid; } else r=mid-1; } cout return 0; }` C++ C. 树上奇偶距离 可以发现，数一定是二分图， 而距离是偶数时，两点同色， 距离是奇数时，两点异色。 根据性质建树即可，但是细节比较多， （去重写的有点麻烦了，甚至多此一举写了一个重载运算符） 代码： #include using namespace std; #define int long long const int N=55; int n; struct node{ int x,y; bool operator ==(node &a){ return a.x==x&&a.y==y; } }; vector t[N],sg[N],ug[N],sum[3]; vector ans; char a[N][N]; int col[N]; bool dfs(int u,int c){ col[u]=c; for(int i=0;i>n; for(int i=0;i>a[i][j]; for(int i=0;iy) swap(x,y); ans.push_back((node){x,y}); } for(int i=0;iy) swap(x,y); ans.push_back({x,y}); } for(int i=0;i `#include using namespace std; #define int long long const int N=55; int n; struct node{ int x,y; bool operator ==(node &a){ return a.x==x&&a.y==y; } }; vectorint> t[N],sg[N],ug[N],sum[3]; vector ans; char a[N][N]; int col[N]; bool dfs(int u,int c){ col[u]=c; for(int i=0;isg[u].size();i++){ int v=sg[u][i]; if(!col[v]&&!dfs(v,c)) return 0; if(col[v]!=c) return 0; } for(int i=0;iug[u].size();i++){ int v=ug[u][i]; if(!col[v]&&!dfs(v,3-c)) return 0; if(col[v]==c) return 0; } return 1; } signed main(){ cin>>n; for(int i=0;ifor(int j=0;j>a[i][j]; for(int i=0;ifor(int j=0;j if(a[i][j]=='E'){ sg[i].push_back(j); sg[j].push_back(i); } else if(a[i][j]=='O'){ ug[i].push_back(j); ug[j].push_back(i); } } if(!dfs(0,1)){ cout1; return 0; } for(int i=1;i if(!col[i]) if(!dfs(i,2)){ cout1; return 0; } } for(int i=0;isum[col[i]].push_back(i); if(!sum[1].size()||!sum[2].size()){ cout1; return 0; } for(int i=0;isum[2].size();i++){ int x=sum[1][0],y=sum[2][i]; if(x>y) swap(x,y); ans.push_back((node){x,y}); } for(int i=0;isum[1].size();i++){ int x=sum[2][0],y=sum[1][i]; if(x>y) swap(x,y); ans.push_back({x,y}); } for(int i=0;ians.size();i++){ for(int j=0;jans.size();j++){ if(i==j) continue; node x=ans[i],y=ans[j]; if(x==y&&x.x+x.y!=0) ans[i].x=ans[i].y=0; } } for(int i=0;ians.size();i++){ node x=ans[i]; if(x.x!=0||x.y!=0) coutx.x" "x.y" "; } return 0; }` C++
二分图与网络流初步
笔记