3.11 无向图的双连通分量
3.11.1 395. 冗余路径
代码：
#include<bits/stdc++.h> using namespace std; const int N=5010,M=20010; int n,m; int dfn[N],low[N],timestamp; stack<int> stk; int id[N],dcc_cnt; bool is_bridge[M]; int d[N]; int h[N],e[M],ne[M],idx; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void tarjan(int u,int from) { dfn[u]=low[u]=++timestamp; stk.push(u); for(int i=h[u];i!=-1;i=ne[i]) { int j=e[i]; if(!dfn[j]) { tarjan(j,i); low[u]=min(low[u],low[j]); if(dfn[u]<low[j]) { is_bridge[i]=is_bridge[i^1]=true; } } else if(i!=(from^1)) low[u]=min(low[u],dfn[j]); } if(dfn[u]==low[u]) { ++dcc_cnt; int y; do{ y=stk.top(); stk.pop(); id[y]=dcc_cnt; }while(y!=u); } } int main() { memset(h,-1,sizeof h); cin>>n>>m; while(m--) { int a,b; cin>>a>>b; add(a,b),add(b,a); } tarjan(1,-1); for(int i=0;i<idx;i++) { if(is_bridge[i]) d[id[e[i]]]++; } int cnt=0; for(int i=1;i<=dcc_cnt;i++) if(d[i]==1) cnt++; cout<<(cnt+1)/2; return 0; }
3.11.2 1183. 电力
代码：
#include<bits/stdc++.h> using namespace std; const int N=100010,M=300010; int n,m; int dfn[N],low[N],timestamp; int root,ans; int h[N],e[M],ne[M],idx; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void tarjan(int u) { dfn[u]=low[u]=++timestamp; int cnt=0; for(int i=h[u];i!=-1;i=ne[i]) { int j=e[i]; if(!dfn[j]) { tarjan(j); low[u]=min(low[u],low[j]); if(low[j]>=dfn[u]) cnt++; } else low[u]=min(low[u],dfn[j]); } if(u!=root) cnt++; ans=max(ans,cnt); } int main() { while(true) { cin>>n>>m; if(n==0&&m==0) break; memset(h,-1,sizeof h); memset(dfn,0,sizeof dfn); idx=timestamp=0; while(m--) { int a,b; cin>>a>>b; add(a,b),add(b,a); } ans=0; int cnt=0; for(root=0;root<n;root++) { if(!dfn[root]) { cnt++; tarjan(root); } } cout<<ans+cnt-1<<endl; } return 0; }
3.11.3 396. 矿场搭建
代码：
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ULL; const int N=1010,M=1010; int n,m; int dfn[N],low[N],timestamp; stack<int> stk; int dcc_cnt; vector<int> dcc[N]; bool cut[N]; int root; int h[N],e[M],ne[M],idx; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void tarjan(int u) { dfn[u]=low[u]=++timestamp; stk.push(u); if(u==root&&h[u]==-1) { dcc_cnt++; dcc[dcc_cnt].push_back(u); return; } int cnt=0; for(int i=h[u];i!=-1;i=ne[i]) { int j=e[i]; if(!dfn[j]) { tarjan(j); low[u]=min(low[u],low[j]); if(dfn[u]<=low[j]) { cnt++; if(u!=root||cnt>1) cut[u]=true; ++dcc_cnt; int y; do{ y=stk.top(); stk.pop(); dcc[dcc_cnt].push_back(y); }while(y!=j); dcc[dcc_cnt].push_back(u); } } else low[u]=min(low[u],dfn[j]); } } int main() { int T=1; while(true) { cin>>m; if(m==0) break; memset(h,-1,sizeof h); memset(dfn,0,sizeof dfn); memset(cut,0,sizeof cut); for(int i=0;i<N;i++) dcc[i].clear(); idx=n=timestamp=dcc_cnt=0; while(m--) { int a,b; cin>>a>>b; add(a,b),add(b,a); n=max(n,a); n=max(n,b); } for(root=1;root<=n;root++) { if(!dfn[root]) tarjan(root); } int res=0; ULL num=1; for(int i=1;i<=dcc_cnt;i++) { int cnt=0; for(int j=0;j<dcc[i].size();j++) { if(cut[dcc[i][j]]) cnt++; } if(cnt==0) { if(dcc[i].size()>1) res+=2,num*=dcc[i].size()*(dcc[i].size()-1)/2; else res++; } else if(cnt==1) res++,num*=dcc[i].size()-1; } cout<<"Case "<<T<<": "<<res<<" "<<num<<endl; T++; } return 0; }
3.12 二分图
3.12.1 257. 关押罪犯
代码：
#include<bits/stdc++.h> using namespace std; const int N=20010,M=200010; int n,m; int color[N]; //0表示未染色，1表示染白色，2表示染黑色 int h[N],e[M],w[M],ne[M],idx; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } bool dfs(int u,int c,int mid) { color[u]=c; for(int i=h[u];i!=-1;i=ne[i]) { int j=e[i]; if(w[i]<=mid) continue; if(color[j]) { if(color[j]==c) return false; } else if(!dfs(j,3-c,mid)) return false; } return true; } bool check(int mid) { memset(color,0,sizeof color); for(int i=1;i<=n;i++) { if(!color[i]) { if(!dfs(i,1,mid)) return false; } } return true; } int main() { memset(h,-1,sizeof h); cin>>n>>m; while(m--) { int a,b,c; cin>>a>>b>>c; add(a,b,c),add(b,a,c); } int l=0,r=1e9; while(l<r) { int mid=(l+r)/2; if(check(mid)) r=mid; else l=mid+1; } cout<<r; return 0; }
3.12.2 372. 棋盘覆盖
代码：
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; const int N=110; int n,t; PII match[N][N]; int g[N][N]; bool st[N][N]; int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; bool findG(int x,int y) { for(int i=0;i<4;i++) { int a=x+dx[i],b=y+dy[i]; if(a<1||a>n||b<1||b>n) continue; if(st[a][b]||g[a][b]) continue; st[a][b]=true; PII t=match[a][b]; if(t.first==-1||findG(t.first,t.second)) { match[a][b]=make_pair(x,y); return true; } } return false; } int main() { cin>>n>>t; while(t--) { int x,y; cin>>x>>y; g[x][y]=true; } memset(match,-1,sizeof match); int res=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if((i+j)%2&&!g[i][j]) { memset(st,0,sizeof st); if(findG(i,j)) res++; } } } cout<<res; return 0; }
3.12.3 376. 机器任务
代码：
#include<bits/stdc++.h> using namespace std; const int N=110; int n,m,k; int match[N]; bool g[N][N],st[N]; bool findG(int x) { for(int i=1;i<m;i++) { if(!st[i]&&g[x][i]) { st[i]=true; if(match[i]==-1||findG(match[i])) { match[i]=x; return true; } } } return false; } int main() { while(true) { cin>>n; if(n==0) break; cin>>m>>k; memset(g,0,sizeof g); memset(match,-1,sizeof match); while(k--) { int t,a,b; cin>>t>>a>>b; if(!a||!b) continue; g[a][b]=true; } int res=0; for(int i=1;i<n;i++) { memset(st,0,sizeof st); if(findG(i)) res++; } cout<<res<<endl; } return 0; }
3.12.4 378. 骑士放置
代码：
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; const int N=110; int n,m,t; int g[N][N]; PII match[N][N]; bool st[N][N]; int dx[8]={-2,-1,1,2,2,1,-1,-2},dy[8]={1,2,2,1,-1,-2,-2,-1}; bool findG(int x,int y) { for(int i=0;i<8;i++) { int a=x+dx[i],b=y+dy[i]; if(a<1||a>n||b<1||b>m) continue; if(st[a][b]||g[a][b]) continue; st[a][b]=true; PII t=match[a][b]; if(t.first==-1||findG(t.first,t.second)) { match[a][b]=make_pair(x,y); return true; } } return false; } int main() { cin>>n>>m>>t; for(int i=0;i<t;i++) { int x,y; cin>>x>>y; g[x][y]=true; } memset(match,-1,sizeof match); int res=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if((i+j)%2&&!g[i][j]) { memset(st,0,sizeof st); if(findG(i,j)) res++; } } } cout<<n*m-res-t; return 0; }
3.12.5 379. 捉迷藏
代码：
#include<bits/stdc++.h> using namespace std; const int N=210; int n,m; int match[N]; bool st[N],d[N][N]; bool findG(int x) { for(int i=1;i<=n;i++) { if(d[x][i]&&!st[i]) { st[i]=true; int t=match[i]; if(t==0||findG(t)) { match[i]=x; return true; } } } return false; } int main() { cin>>n>>m; for(int i=0;i<m;i++) { int a,b; cin>>a>>b; d[a][b]=true; } //求传递闭包 for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]|=d[i][k]&d[k][j]; int res=0; for(int i=1;i<=n;i++) { memset(st,0,sizeof st); if(findG(i)) res++; } cout<<n-res; return 0; }
