[HDU 3313]最大流、有向图有源汇的割点**

【题目大意】给定一个有向图和源汇,求图中割点的个数

【算法分析】这题比较神,做法是将每个点拆点,然后中间连边流量为1,图中的边连边流量为inf,然后比较特殊的是S和T所拆得点间流量为2。然后这样的话,如果流量为2,那么图中除了S和T没有割点。如果流量为1,那么增广路上的有可能是割点,然后利用求最小割的dfs算法求出各个割。如果流量为0的话,那么说明S和T本来就不连通,所以任何一个点都是割点。

【其它】1WA,因为flow=2时特判错了,写成了0.低级错误啊...

2078969 2010-02-09 15:56:54 Accepted 3313 3156MS 12964K 2496 B G++ cwj

【CODE】

#include #include const int N=222222;
const
int inf=(0x7FFFFFFF-10)/2;
struct
gtp{int x,y,c,op,next;}g[1000000];
int
n,m,e,S,T,ls[N],fa[N],v[N],list[N],ans,zgl[N],tt;

void addedge(int x,int y,int c){
    e++;
    g[e].x=x; g[e].y=y; g[e].c=c; g[e].op=e+1;
    g[e].next=ls[x]; ls[x]=e;
    e++;
    g[e].x=y; g[e].y=x; g[e].c=0; g[e].op=e-1;
    g[e].next=ls[y]; ls[y]=e;
}
   

void init(){
    e=0;
    memset(ls,0,sizeof(ls));
    memset(zgl,0,sizeof(zgl));
    for
(int i=1;i<=m;i++){
        int
x,y;
        scanf("%d%d",&x,&y);
        addedge(x+n,y,inf);
    }

    scanf("%d%d",&S,&T);
    for
(int i=0;i<n;i++)
      if
(i!=S && i!=T) addedge(i,i+n,1);
                   else
addedge(i,i+n,2);
    T+=n;
}

bool bfs(){
    for
(int i=0;i<2*n;i++) v[i]=0;
    int
head=0,tail=1;
    list[1]=S;
    while
(head!=tail){
        head++;
        for
(int t=ls[list[head]];t;t=g[t].next)
          if
(!v[g[t].y] && g[t].c){
              v[g[t].y]=1;
              tail++;
              list[tail]=g[t].y;
              fa[g[t].y]=t;
          }
    }

    if
(v[T]) return true;
    return
false;
}
   

void change(){
    for
(int i=T;i!=S;i=g[fa[i]].x){
        g[fa[i]].c--;
        g[g[fa[i]].op].c++;
        zgl[i]=1;
    }
   
    zgl[S]=1;
}
   

int ek(){
    bool
flag=bfs();
    if
(!bfs()) return 0;
    change();
    flag=bfs();
    if
(!bfs()) return 1;
    return
2;
}
   

void dfs(int k){
    tt++;
    list[tt]=k;
    v[k]=1;
    for
(int t=ls[k];t;t=g[t].next)
      if
(g[t].c && !v[g[t].y]) dfs(g[t].y);
}
   

void work(){
    g[ls[S]].c=0;
    g[ls[T-n]].c=0;
    memset(v,0,sizeof(v));
    ans=0;
    int
st=S;
    for
(;;){
        tt=0;
        dfs(st);
        bool
flag=false;
        for
(int i=1;i<=tt;i++) if (!flag)
          for
(int t=ls[list[i]];t;t=g[t].next)
            if
((t&1) && !g[t].c && !v[g[t].y]){
                ans++;
                flag=true;
                st=g[t].y;
                if
(g[t].y==T) return;
            }   
    }   
}
   

int main(){
    while
(scanf("%d%d",&n,&m)!=EOF){
        init();
        if
(S+n==T){
            printf("1n");
            continue
;
        }
   
        int
flow=ek();
        if
(flow==0) printf("%dn",n);
        else
        if
(flow==2) printf("2n");
        else
{
            work();
            printf("%dn",ans);
        }   
    }   
}
   

加入对话

1条评论

留下评论

您的电子邮箱地址不会被公开。