ECNU1101-Dinic

题意：从起点到终点有几条特殊路径。
特殊路径指的是：对于任意两条路径，他们的与起点相连的点是不同的点 && 与终点的相连的点是不同的点。
  1 /*
  2 题意：从起点到终点有几条特殊路径。
  3 特殊路径指的是：对于任意两条路径，他们的与起点相连的点是不同的点 && 与终点的相连的点是不同的点。
  4 思路:
  5     把起点和后继节点的流量设置为1，同理对终点处理
  6     这样在寻找最大流的增广路径时就会消除一条。。
  7 */
  8 #include<stdio.h>
  9 #include<string.h>
 10 #include<stdlib.h>
 11 #include<algorithm>
 12 #include<queue>
 13 #include<iostream>
 14 using namespace std;
 15 const int maxn = 205;
 16 const int maxm = maxn*maxn;
 17 const int inf = 0x3f3f3f3f;
 18 struct Edge{
 19     int u,v,next,val;
 20 }edge[ maxm ];
 21 int cnt,head[ maxn ];
 22 int q[ maxn+5 ];
 23 int lev[ maxn+5 ];
 24 
 25 void init(){
 26     cnt = 0;
 27     memset( head,-1,sizeof( head ) );
 28 }
 29 void addedge( int a,int b,int c ){
 30     edge[ cnt ].u = a;
 31     edge[ cnt ].v = b;
 32     edge[ cnt ].val = c;
 33     edge[ cnt ].next = head[ a ];
 34     head[ a ] = cnt ++;
 35 }
 36 
 37 bool bfs( int src,int dest,int n ){
 38     int head2 = 0,tail2 = 0;
 39     q[ tail2++ ] = src;
 40     memset( lev,-1,sizeof( lev ) );
 41     lev[ src ] = 0;
 42     while( head2<tail2 ){
 43         int cur = q[ head2++ ];
 44         for( int i=head[ cur ];i!=-1;i=edge[ i ].next ){
 45             int nxt = edge[ i ].v;
 46             if( edge[ i ].val>0 && lev[ nxt ]==-1 ){
 47                 lev[ nxt ] = lev[ cur ] + 1;
 48                 q[ tail2++ ] = nxt;
 49             }
 50         }
 51     }
 52     if( lev[ dest ]==-1 ) return false;
 53     else return true;
 54 }
 55 
 56 int Dinic( int src,int dest,int n ){
 57     int maxFlow = 0;
 58     while( true ){
 59         if( bfs( src,dest,n )==false ) 
 60             break;
 61         //printf("ok
");
 62         int id = src;
 63         int tail = 0;
 64         while( true ){
 65             if( id==dest ){
 66                 int flow = inf;
 67                 int flag = -1;
 68                 for( int i=0;i<tail;i++ ){
 69                     if( edge[ q[ i ] ].val<flow ){
 70                         flow = edge[ q[ i ] ].val ;
 71                         flag = i;
 72                     }
 73                 }
 74                 for( int i=0;i<tail;i++ ){
 75                     edge[ q[ i ] ].val -= flow;
 76                     edge[ q[ i ]^1 ].val += flow;
 77                 }
 78                 if( flag==-1 ) {
 79                 //    printf("Un_Normal
");
 80                     return inf;
 81                 }
 82                 else{
 83                     maxFlow += flow;
 84                     tail = flag;
 85                     id = edge[ q[ flag ] ].u;
 86                 }
 87             }
 88             //solve maxFlow
 89             id = head[ id ];
 90             while( id!=-1 ){
 91                 if( edge[ id ].val>0 && lev[ edge[id].u ]+1==lev[ edge[id].v ] ){
 92                     break;
 93                 }
 94                 id = edge[ id ].next;
 95             }
 96             if( id!=-1 ){
 97                 q[ tail++ ] = id;
 98                 id = edge[ id ].v;
 99             }
100             else{
101                 if( tail==0 ) break;
102                 lev[ edge[ q[ tail-1 ] ].v ] = -1;
103                 id = edge[ q[ --tail ] ].u;
104             }
105         }
106     }
107     //printf("Normal:
");
108     return maxFlow;
109 }
110           
111 
112 int main(){
113     //freopen( "in.txt","r",stdin );
114     int n;
115     //printf("ok
");
116     while( scanf("%d",&n)==1 ){
117         init();
118         int cc;
119         int u,v;
120         //printf("begin input
");
121         for( int i=1;i<n;i++ ){
122             scanf("%d",&cc);
123             //printf("cc = %d
",cc);
124             u = i;
125             while( cc-- ){
126                 scanf("%d",&v);
127                 if( u==1||v==n ){
128                     addedge( u,v,1 );
129                     addedge( v,u,0 );
130                 }
131                 else{
132                     addedge( u,v,inf );
133                     addedge( v,u,0 );
134                 }
135             }
136         }
137         int src = 1;
138         int dest = n;
139         //printf("begin
");
140         printf("%d
",Dinic( src,dest,n ));
141     }
142     return 0;
143 }
View Code
keep moving...