先寫一道，USACO5.4.5telecow求圖的最小點(diǎn)割，運(yùn)用拆點(diǎn)法（同求圖的最小路徑覆蓋），然后求最小割。
我采用了一種流量*6000+序號i的方法，但好像有問題，如果真的要寫的話就像上面一道最小割一樣在DFS一下。
說明：兩種搜索
1.論文中的floodfill（BFS/DFS）求該最大流的最小割。
2.DFS枚舉割點(diǎn)，求最大流為0，表示s->t不通（或直接BFS驗(yàn)證不通）。
不知對不對的代碼
/**//*
USER:zyn19961
TASK:telecow
LANG:C++
*/
#include<cstdio>
#include<cstring>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
//
#define MM(a,i) memset(a,i,sizeof(a))
#define FOR(i,l,r) for (int i=(l);i<=(r);i++)
#define DFOR(i,r,l) for (int i=(r);i>=(l);i--)
#define NFOR(i,l,r) for (i=(l);i<=(r);i++)
#define NDFOR(i,r,l) for (i=(r);i>=(l);i--)
#define PFOR(p,a,next) for(int p=a;p;p=next[p])
#define NPFOR(p,a,next) for(p=a;p;p=next[p])
//
typedef long long Int64;
const int INF=~0U>>2;
//
const int maxn=601;
const int maxm=300001;
//
int Q[maxm],H,T;
//
int to[maxm],next[maxm],sc[maxm],snum=0;
int level[maxn],head[maxn],out[maxn];
//
void init();
void insert(int x,int y,int c);
int max_flow(int n,int s,int t);
//
ifstream fin("telecow.in");
ofstream fout("telecow.out");
//
//
int main()
{//a in a+n out
int n,m;fin>>n>>m;
int c1,c2;fin>>c1>>c2;
int a,b;init();
FOR(i,1,n)insert(i,i+n,6000+i);
FOR(i,1,m)fin>>a>>b,insert(a+n,b,INF),insert(b+n,a,INF);
int ans=max_flow(n+n,c1+n,c2);
ans/=6000;
fout<<ans<<"\n";
//
bool arr[maxn];MM(arr,false);
H=T=1,Q[H]=c1+n,arr[c1+n]=true;
for(;H<=T;){
PFOR(p,head[Q[H]],next)
if(sc[p]&&!arr[to[p]])T++,Q[T]=to[p],arr[to[p]]=true;
H++;
}
FOR(i,1,n){
if(arr[i]!=arr[i+n]&&i!=c1&&i!=c2)
if(ans>1)fout<<i<<" ",ans--;
else if(ans==1)fout<<i<<"\n",ans--;
else break;
}
//
fout.close();
return 0;
}
void init(){snum=1;MM(head,0);}
void insert(int x,int y,int c){
snum++,to[snum]=y,sc[snum]=c,next[snum]=head[x],head[x]=snum;
snum++,to[snum]=x,sc[snum]=0,next[snum]=head[y],head[y]=snum;}
int max_flow(int n,int s,int t){
int flow=0,cur;
for(;;){MM(level,0);
H=T=1,level[s]=1,Q[H]=s;
for(;H<=T;H++){int &t=Q[H];
PFOR(p,head[t],next)
if(sc[p]&&!level[to[p]])
T++,level[to[p]]=level[t]+1,Q[T]=to[p];}
if(!level[t])break;
FOR(i,1,n)out[i]=head[i];
for(int q=0;;){
if(!q){
NPFOR(cur,out[s],next)
if(sc[cur]&&out[to[cur]]&&level[to[cur]]==2)
break;
if(cur)q++,Q[q]=cur,out[s]=next[cur];
else break;
}
int u=to[Q[q]];
if(u==t){int dd=INF,ddl=0;
FOR(i,1,q)if(sc[Q[i]]<dd)dd=sc[Q[i]],ddl=i;
flow+=dd;
FOR(i,1,q)sc[Q[i]]-=dd,sc[Q[i]^1]+=dd;
FOR(i,1,q)if(!sc[Q[i]]){q=ddl-1;break;}
}
else {
NPFOR(cur,out[u],next)
if(sc[cur]&&out[to[cur]]&&level[u]+1==level[to[cur]])break;
if(cur)q++,Q[q]=cur,out[u]=next[cur];
else out[u]=0,q--;
}
}
}
return flow;
}
另一道是5.3.3schlnet,與圖的強(qiáng)連通分量有關(guān)。
方法實(shí)在太多了,準(zhǔn)備一一實(shí)現(xiàn)后再深入總結(jié)。
1.floyd O（n^3）
2.tarjianO(m+n)
3.dfn-low O(m+n)
4.Kosaraju O((m+n)*2)
我的代碼（dfn_low）
/**//*
USER:zyn19961
TASK:schlnet
LANG:C++
*/
#include<cstdio>
#include<cstring>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
//
#define MM(a,i) memset(a,i,sizeof(a))
#define FOR(i,l,r) for (int i=(l);i<=(r);i++)
#define DFOR(i,r,l) for (int i=(r);i>=(l);i--)
//
typedef long long Int64;
const int INF=~0U>>2;
const int maxn=201;
//
ifstream fin("schlnet.in");
ofstream fout("schlnet.out");
//
int n,a,b;
int G[maxn][maxn];
int dfn[maxn],low[maxn];
int tot=0;
int st=0,stack[maxn];
bool in_stack[maxn];
int set[maxn];
void group(int u);
int map[maxn][maxn];
int totset=0;
int main(){
fin>>n;
MM(in_stack,false),MM(dfn,0),MM(map,0);
FOR(i,1,n){
int a=INF;
for(;a!=0;)
fin>>a,G[i][0]++,G[i][G[i][0]]=a;
G[i][0]--;
}
FOR(i,1,n)if(!dfn[i])group(i);
FOR(i,1,n)
FOR(j,1,G[i][0]){
a=set[i],b=set[G[i][j]];
if(map[a][b]==0&&a!=b){
map[a][b]=1;
map[a][0]++;
map[b][totset+1]++;
}
}
int count1=0,count2=0;
FOR(i,1,totset){
if(map[i][totset+1]==0)count1++;
if(map[i][0]==0)count2++;
}
fout<<count1<<"\n";
if(totset==1)fout<<"0\n";
else fout<<max(count1,count2)<<"\n";
fin.close();
fout.close();
return 0;
}
void group(int u){
tot++;
dfn[u]=low[u]=tot;
st++,stack[st]=u;
in_stack[u]=true;
FOR(i,1,G[u][0]){
int v=G[u][i];
if(!dfn[v]){
group(v);
if(low[v]<low[u])
low[u]=low[v];
}
if(dfn[v]<low[u])
if(in_stack[v])
low[u]=dfn[v];
}
if(dfn[u]==low[u]){
totset++;
for(;stack[st+1]!=u;st--)
set[stack[st]]=totset,in_stack[stack[st]]=false;
}
}