这我没什么好说的,那天补个证明
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int m,n,tot=-1,h[10005],ans=0; 5 struct node{ 6 int from,next,to,rest; 7 int last; 8 }e[100005]; 9 int hou[10005]; 10 bool judge[10005]; 11 void add(int x,int y,int z){ 12 tot++; 13 e[tot].next=h[x]; 14 h[x]=tot; 15 e[tot].from=x; 16 e[tot].to=y; 17 e[tot].rest=z; 18 } 19 20 int dis[10005],g[10005],flow[10005]; 21 bool vis[10005]; 22 23 int bfs(int s,int t){ 24 queue<int>q; 25 dis[s]=0; 26 q.push(s);vis[s]=true; 27 while(!q.empty()){ 28 int u=q.front();vis[u]=false;q.pop(); 29 for(int i=h[u];i!=(-1);i=e[i].next){ 30 if(dis[e[i].to]>dis[u]+1&&g[e[i].to]==(-1)&&e[i].rest>0){ 31 g[e[i].to]=i; 32 flow[e[i].to]=min(flow[u],e[i].rest); 33 dis[e[i].to]=dis[u]+1; 34 if(vis[e[i].to]==false){ 35 vis[e[i].to]=true; 36 q.push(e[i].to); 37 } 38 } 39 } 40 } 41 } 42 43 int EK(int s,int t){ 44 while(1){ 45 memset(dis,0x7f,sizeof(dis)); 46 memset(vis,false,sizeof(vis)); 47 memset(flow,0x7f,sizeof(flow)); 48 memset(g,-1,sizeof(g)); 49 bfs(s,t); 50 if(g[t]==(-1))return 0; 51 ans+=flow[t]; 52 for(int p=t;p!=(s);p=e[g[p]].from){ 53 e[g[p]].rest-=flow[t]; 54 e[g[p]^1].rest+=flow[t]; 55 } 56 57 } 58 } 59 60 int main(){ 61 //freopen("shut1.in","r",stdin); 62 memset(h,(-1),sizeof(h)); 63 cin>>n>>m; 64 for(int i=1;i<=n;i++){ 65 add(0,i,1); 66 add(i,0,0); 67 } 68 for(int i=1;i<=m;i++){ 69 int x,y;cin>>x>>y; 70 add(x,n+y,1); 71 add(n+y,x,0); 72 } 73 for(int i=1;i<=n;i++){ 74 add(i+n,2*n+1,1); 75 add(2*n+1,i+n,0); 76 } 77 EK(0,2*n+1); 78 for(int i=1;i<=n;i++){ 79 for(int j=h[i];j!=(-1);j=e[j].next){ 80 if(e[j].rest==0&&e[j].to!=0){ 81 hou[i]=e[j].to-n; 82 break; 83 } 84 } 85 } 86 memset(judge,false,sizeof(judge)); 87 for(int i=1;i<=n;i++){ 88 if(judge[i]==false){ 89 for(int now=i;now!=(2*n+1)&&now!=0;now=hou[now]){ 90 cout<<now<<" "; 91 judge[now]=true; 92 } 93 cout<<endl; 94 } 95 } 96 cout<<n-ans<<endl; 97 }