T1缩点：
将强连通分量缩为一点
#include<bits/stdc++.h> using namespace std; struct edge{ int u,v; }; edge e[100005],newe[100005]; bool v[10005],vis[10005]; int dfn[10005],n,m,f[10005],ne[100005],k[10005],now,low[10005],s[10005],top,zz[10005],newf[10005],newne[100005],newn,newm,newk[10005],scc[10005],dp[10005]; //scc:相同时间点的位置 inline int read(){ int k=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) k=k*10+c-'0'; return k*f; } inline void tarjan(int x){ dfn[x]=low[x]=++now; s[++top]=x; v[x]=true; for(int i=f[x];i;i=ne[i]){ int y=e[i].v; if(!dfn[y]){ tarjan(y); low[x]=min(low[x],low[y]); } else if(dfn[y]&&v[y]) low[x]=min(low[x],dfn[y]); } if(low[x]==dfn[x]){ while(s[top]!=x) v[s[top]]=false,s[top]=0,top--; v[x]=false; s[top]=0; top--; } return ; } int main(){ n=read(),m=read(); for(int i=1;i<=n;i++) k[i]=read(); for(int i=1;i<=m;i++){ e[i].u=read(),e[i].v=read(); ne[i]=f[e[i].u]; f[e[i].u]=i; } for(int i=1;i<=n;i++) if(!dfn[i]) zz[i]=true,tarjan(i); // for(int i=1;i<=n;i++) // cout<<dfn[i]<<" "<<low[i]<<endl; for(int i=1;i<=n;i++){ if(!scc[low[i]]){ newn++; scc[low[i]]=newn; } newk[scc[low[i]]]+=k[i]; } for(int i=1;i<=n;i++){ for(int j=f[i];j;j=ne[j]){ int c=e[j].v; if(scc[low[c]]!=scc[low[i]]){ newm++; newe[newm].u=scc[low[i]]; newe[newm].v=scc[low[c]]; newne[newm]=newf[scc[low[i]]]; newf[scc[low[i]]]=newm; } } } for(int i=1;i<=newn;i++){ cout<<i<<":"<<newk[i]<<endl; for(int j=newf[i];j;j=newne[j]) cout<<newe[j].v<<" "; cout<<endl; } }
T2二分图最大匹配：
二分图
感谢@一扶苏一 提供的hack数据
给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数
输入格式：
第一行，n,m,e
第二至e+1行，每行两个正整数u,v，表示u,v有一条连边
输出格式：
共一行，二分图最大匹配
输入样例#1： 复制
1 1 1 1 1输出样例#1： 复制
1n,m \leq 1000n,m≤1000， 1 \leq u \leq n1≤u≤n， 1 \leq v \leq m1≤v≤m ，e \le n\times me≤n×m
因为数据有坑，可能会遇到 v>mv>m 或者 u>nu>n 的情况。请把 v>mv>m 或者 u>nu>n 的数据自觉过滤掉。
算法：二分图匹配
#include<bits/stdc++.h> using namespace std; int bs,n,m,s,t,f[10005],ne[800005],d[10005],maxflow,x,y; queue<int>q; struct edge{ int u,v,c,f; }e[800005]; inline int read(){ int k=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) k=k*10+c-'0'; return k*f; } inline bool bfs(){ memset(d,0,sizeof(d)); while(q.size()) q.pop(); q.push(s); d[s]=1; while(q.size()){ int x=q.front();q.pop(); for(int i=f[x];i;i=ne[i]) if(e[i].f&&!d[e[i].v]){ q.push(e[i].v); d[e[i].v]=d[x]+1; if(e[i].v==t) return true; } } return false; } inline int dinic(int x,int flow){ if(x==t) return flow; int rest=flow,k; for(int i=f[x];i&&rest;i=ne[i]){ if(e[i].f&&d[e[i].v]==d[x]+1){ k=dinic(e[i].v,min(rest,e[i].f)); if(!k) d[e[i].v]=0; e[i].f-=k; e[i+1].f+=k; rest-=k; } } return flow-rest; } int main(){ n=read(),m=read(),bs=read(); s=n+m+1,t=n+m+2; for(int i=1;i<=bs*2;i+=2){ x=read(),y=read(); if(x>n||y>m) continue; e[i+1].v=e[i].u=x,e[i+1].u=e[i].v=y+n;e[i].f=1; ne[i]=f[e[i].u],f[e[i].u]=i; e[i+1].f=0; ne[i+1]=f[e[i+1].u],f[e[i+1].u]=i+1; } for(int i=bs*2+1;i<=(bs+n)*2;i+=2){ e[i].u=s,e[i].v=(i-bs*2)/2+1; e[i].f=1; e[i+1].u=(i-bs*2)/2+1; e[i+1].v=s; e[i+1].f=0; ne[i]=f[e[i].u],f[e[i].u]=i; ne[i+1]=f[e[i+1].u],f[e[i+1].u]=i+1; } for(int i=(bs+n)*2+1;i<=(bs+m+n)*2;i+=2){ e[i+1].u=t,e[i+1].v=(i-(bs+n)*2)/2+1+n; e[i].f=1; e[i].u=(i-(bs+n)*2)/2+1+n; e[i].v=t; e[i+1].f=0; ne[i]=f[e[i].u],f[e[i].u]=i; ne[i+1]=f[e[i+1].u],f[e[i+1].u]=i+1; } int flow=0; while(bfs()) while(flow=dinic(s,1e9)) maxflow+=flow; cout<<maxflow; return 0; }
T3网络最大流：
如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。
输入格式：
第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来M行每行包含三个正整数ui、vi、wi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi）
输出格式：
一行，包含一个正整数，即为该网络的最大流。
输入样例#1： 复制
4 5 4 3 4 2 30 4 3 20 2 3 20 2 1 30 1 3 40输出样例#1： 复制
50时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=10，M<=25
对于70%的数据：N<=200，M<=1000
对于100%的数据：N<=10000，M<=100000
样例说明：
题目中存在3条路径：
4-->2-->3，该路线可通过20的流量
4-->3，可通过20的流量
4-->2-->1-->3，可通过10的流量（边4-->2之前已经耗费了20的流量）
故流量总计20+20+10=50。输出50
#include<bits/stdc++.h> using namespace std; int n,m,s,t,f[10005],ne[200005],d[10005],maxflow; queue<int>q; struct edge{ int u,v,c,f; }e[200005]; inline int read(){ int k=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) k=k*10+c-'0'; return k*f; } inline bool bfs(){ memset(d,0,sizeof(d)); while(q.size()) q.pop(); q.push(s); d[s]=1; while(q.size()){ int x=q.front();q.pop(); for(int i=f[x];i;i=ne[i]) if(e[i].f&&!d[e[i].v]){ q.push(e[i].v); d[e[i].v]=d[x]+1; if(e[i].v==t) return true; } } return false; } inline int dinic(int x,int flow){ if(x==t) return flow; int rest=flow,k; for(int i=f[x];i&&rest;i=ne[i]){ if(e[i].f&&d[e[i].v]==d[x]+1){ k=dinic(e[i].v,min(rest,e[i].f)); if(!k) d[e[i].v]=0; e[i].f-=k; e[i+1].f+=k; rest-=k; } } return flow-rest; } int main(){ n=read(),m=read(),s=read(),t=read(); for(int i=1;i<=m*2;i+=2){ e[i+1].v=e[i].u=read(),e[i+1].u=e[i].v=read();e[i].f=read(); ne[i]=f[e[i].u],f[e[i].u]=i; e[i+1].f=0; ne[i+1]=f[e[i+1].u],f[e[i+1].u]=i+1; } int flow=0; while(bfs()) while(flow=dinic(s,1e9)) maxflow+=flow; cout<<maxflow; return 0; }
T4割点：
割点
给出一个nn个点，mm条边的无向图，求图的割点。
输入格式：
第一行输入n,mn,m
下面mm行每行输入x,yx,y表示xx到yy有一条边
输出格式：
第一行输出割点个数
第二行按照节点编号从小到大输出节点，用空格隔开
输入样例#1： 复制
6 7 1 2 1 3 1 4 2 5 3 5 4 5 5 6输出样例#1： 复制
1 5对于全部数据，n \le 20000n≤20000，m \le 100000m≤100000
点的编号均大于00小于等于nn。
tarjan图不一定联通。
#include<bits/stdc++.h> using namespace std; struct edge{ int u,v; }e[2000005]; bool v[200005],pd,zz[200005],ans[200005]; int n,m,f[200005],ne[2000005],dfn[200005],low[200005],now,front[200005],tot,answ; inline int read(){ int k=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) k=k*10+c-'0'; return k*f; } inline void dfs(int x){ low[x]=dfn[x]=++now; int has=0; for(int i=f[x];i;i=ne[i]){ int y=e[i].v; if(!dfn[y]){ dfs(e[i].v); low[x]=min(low[x],low[y]); if(low[y]>=dfn[x]){ has++; if(has>1||!zz[x]){ if(!ans[x]) answ++; ans[x]=true; } } } else low[x]=min(low[x],dfn[y]); } return ; } int main(){ n=read(); m=read(); for(int i=1;i<=2*m;i+=2){ e[i+1].v=e[i].u=read(),e[i+1].u=e[i].v=read(); ne[i]=f[e[i].u],f[e[i].u]=i; ne[i+1]=f[e[i+1].u],f[e[i+1].u]=i+1; } for(int i=1;i<=n;i++){ if(!dfn[i]) zz[i]=true,dfs(i); } // cout<<ans.size()<<endl; // while(ans.size()){ // cout<<-ans.top()<<" "; // ans.pop(); // } cout<<answ<<endl; for(int i=1;i<=n;i++) if(ans[i]) cout<<i<<" "; return 0; }
