Usaco Training Section 5.4 Telecowmunication

一道最小割点集的题目。因为本人比较菜，一开始没想到拆点，没做出来。后来看了题解，才知道拆点做挺方便的

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define inf 1<<29
#define mp make_pair
#define pii pair<int,int>
#define pb push_back
#define r1 rt<<1
#define r2 rt<<1|1
#define ld long double
using namespace std;

inline int read(){
	int x=0;char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x;
}

const int M=1005;
int d[M],n,m,s,t,arc[M][M],tmp[M][M];

inline bool bfs(){
	memset(d,0,sizeof(d));
	queue<int> q;
	q.push(s);d[s]=1;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int v=1;v<=n;++v){
			if(arc[u][v]&&!d[v]){
				d[v]=d[u]+1;
				if(d[t]!=0) return 1;
				q.push(v);
			}
		}
	}
	return 0;
}

inline int dfs(int u,int flow){
	if(u==t) return flow;
	for(int v=1;v<=n;++v){
		if(arc[u][v]&&d[v]==d[u]+1){
			int k=dfs(v,min(flow,arc[u][v]));
			if(k<=0) continue;
			arc[u][v]-=k;
			arc[v][u]+=k;
			return k;
		}
	}
	return 0;
}

inline int dinic(){
	int ans=0;
	while(bfs()){
		while(int di=dfs(s,inf)) ans+=di;
	}
	return ans;
}

int main()
{
	freopen("telecow.in","r",stdin);
	freopen("telecow.out","w",stdout);
	n=read(),m=read(),s=read(),t=read();
	s*=2;t=t*2-1;
	memset(arc,0,sizeof(arc));
	memset(tmp,0,sizeof(tmp));
	for(int i=1;i<=n;++i){
		arc[i*2-1][i*2]=1;
		tmp[i*2-1][i*2]=1;
	}
	n*=2;
	for(int i=1;i<=m;++i){
		int u=read(),v=read();
		arc[u*2][v*2-1]=arc[v*2][u*2-1]=inf;
		tmp[u*2][v*2-1]=tmp[v*2][u*2-1]=inf;
	}
	int ans=dinic();
	printf("%d\n",ans);
	if(!ans){
		puts("0");
		return 0;
	}
	bool f=0;
    for(int i=1;i<=n;i+=2){
    	if(i==s-1||i==t) continue;
    	for(int j=1;j<=n;++j)
    		for(int k=1;k<=n;++k)
    			arc[j][k]=tmp[j][k];
    	arc[i][i+1]=0;
    	if(dinic()==ans-1){
    		--ans;
    		if(f) printf(" ");
    		else f=1;
    		printf("%d",(i+1)/2);
    		tmp[i][i+1]=0;
    	}
    }
    puts("");
    return 0;
}