poj3204Ikki's Story I - Road Reconstruction（最大流求割边）

链接

最大流=最小割  这题是求割边集 dinic求出残余网络 两边dfs分别以源点d找到可达点 再以汇点进行d找到可达汇点的点

如果u,v为割边 那么s->u可达 v->t可达 并且为饱和边

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <queue>

 #include <algorithm>

 using namespace std;

 const int INF = ;

 const int N = ;

 #define M 100005

 struct node

 {

     int u,v,next;

     int w;

 }edge[M],p[M];

 int head[N],t,vis[N],pp[N],dis[N];

 int st,en;

 bool vis1[N],vis2[N];

 void init()

 {

     t=;

     memset(head,-,sizeof(head));

 }

 void add(int u,int v,int w)

 {

     edge[t].u = u;

     edge[t].v = v;

     edge[t].w = w;

     edge[t].next = head[u];

     head[u] = t++;

     edge[t].u = v;

     edge[t].v = u;

     edge[t].w = ;

     edge[t].next = head[v];

     head[v] = t++;

 }

 int bfs()

 {

     int i,u;

     int w;

     memset(dis,,sizeof(dis));

     queue<int>q;

     q.push(st);

     dis[st]=  ;

     while(!q.empty())

     {

         u = q.front();

         q.pop();

         for(i = head[u] ; i != - ; i = edge[i].next)

         {

             int v = edge[i].v;

             w = edge[i].w;

             if(!dis[v]&&w>)

             {

                 dis[v] = dis[u]+;

                 q.push(v);

             }

         }

     }

     if(dis[en]>) return ;

     return ;

 }

 int dfs(int u,int te)

 {

     int i;

     int s;

     if(u==en) return te;

     int tmp = te;

     for(i = head[u] ; i != - ; i = edge[i].next)

     {

         int v = edge[i].v;

         int w = edge[i].w;

         if(w>&&dis[v]==dis[u]+&&(s=dfs(v,min(te,w))))

         {

             edge[i].w-=s;

             edge[i^].w+=s;

             tmp-=s;

         }

     }

     return te-tmp;

 }

 int dinic()

 {

     int flow = ;

     while(bfs())

     {

         flow+=dfs(st,INF);

     }

     return flow;

 }

 void dfs1(int u)

 {

     int i;

     for(i = head[u] ; i != - ; i= edge[i].next)

     if(!vis1[edge[i].v]&&edge[i].w>)

     {

         vis1[edge[i].v] = ;

         dfs1(edge[i].v);

     }

 }

 void dfs2(int u)

 {

     int i;

     for(i = head[u] ; i != - ; i= edge[i].next)

     {

         int v =  edge[i].v;

         //cout<<v<<" "<<edge[i].w<<endl;

         if(!vis2[edge[i].v]&&edge[i^].w>)

         {

         vis2[edge[i].v] = ;

         dfs2(edge[i].v);

         }

     }

 }

 int main()

 {

     int n,m,i;

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         init();

         memset(vis1,,sizeof(vis1));

         memset(vis2,,sizeof(vis2));

         for(i =  ;i <= m; i++)

         {

             int u,v,c;

             scanf("%d%d%d",&u,&v,&c);

             u++,v++;

             add(u,v,c);

         }

         st = ,en = n;

         int kk = dinic();

         //cout<<kk<<endl;

         vis1[st] = ;

         dfs1(st);

         vis2[en] = ;

         dfs2(en);

         int ans = ;

         dinic();

         for(i = ; i < t; i+=)

         {

             int u = edge[i].u;

             int v = edge[i].v;

             int w = edge[i].w;

             //cout<<u<<" "<<v<<" "<<vis1[u]<<" "<<vis2[v]<<endl;

             if(vis1[u]&&vis2[v]&&w<=)

             ans++;

         }

         cout<<ans<<endl;

     }

     return ;

 }