逃跑

Description
    2009年12月5日，闷墩突然降临nsoi，于是nsoi的所有人只好举家搬迁，逃往其他教室上课。每个教室只允许一些人经过，只能留下一些学生(道理应该很简单)。所有的教室是用有向边连接起来的。问题是有多少人能够逃离闷墩的魔掌。

Input
    所有数均为(231-1)以内的自然数。
    第一行两个数n,m(1<n<=200)，为全校教室的个数(包括nsoi)和nsoi的人数。这些教室编号为1到n，其中nsoi的编号为1。接下来(n-1)行，每行两个数，表示从2号教室开始允许经过的人数和能留下的人数，其中留下的人也必须先“经过”这个教室。
    接下来一行一个数k(1<=k<=40000)，表示边的个数。然后k行，每行两个数a,b表示a号教室到b号教室是用有向边连通的。

Output
    一个自然数，为能逃离的人数。

Sample Input
4 20
10 5
20 5
10 10
3
1 2
1 3
2 4

Sample Output
15

还是利用拆点的思路吧，反正就是讲房间拆成两个点，这么乱搞。

  1 #include <iostream>
  2 #include <cstdlib>
  3 #include <cstring>
  4 #include <cstdio>
  5 #include <queue>
  6 using namespace std ;
  7 const int inf = 1 << 30 , maxn = 40000 + 401  , N = 400 + 11;
  8 
  9 int  n , m , s , t , k;
 10 int sum[N][2] , head[N] , cnt , dis[N]  , cur[N];
 11 struct id
 12 {
 13     int nxt , to , vi ;
 14 } edge[maxn<<2] ;
 15 queue < int > Q ;
 16 
 17 
 18 inline void Init( )
 19 {
 20     freopen( "NSOOJ10734.in" , "r" , stdin ) ;
 21     freopen( "NSOOJ10734.out" , "w" , stdout ) ;
 22 }
 23 
 24 
 25 int read( )
 26 {
 27     char ch = getchar( ) ; int k = 1 , ret = 0 ;
 28     while( ch < '0' || ch > '9' ) { if( ch == '-' ) k = -1 ; ch = getchar( ) ;  }
 29     while( ch >= '0' && ch <='9' ) ret = ret * 10 + ch - '0' , ch = getchar( ) ;
 30     return ret * k ;
 31 }
 32 
 33 
 34 void add( int u , int v , int vi )
 35 {
 36     edge[++cnt].to = v , edge[cnt].vi = vi ;
 37     edge[cnt].nxt = head[u] , head[u] = cnt ;
 38 }  
 39 
 40 void input( )
 41 {
 42     n = read( ) , m = read( ) ; cnt = -1 ;
 43     s = n + 1 , t = 402 ; memset( head , -1 , sizeof(head) ) ;
 44     for( int x = 2 ; x <= n ; ++x )
 45     {
 46         sum[x][0] = read( ) , sum[x][1] = read( ) ;
 47         add( x , x + n, sum[x][0] ) ;
 48         add( x + n , x , 0 ) ;
 49         add( x+n , t , sum[x][1] ) ;
 50         add( t , x+n , 0 ) ;
 51     }
 52     k = read( ) ; int a , b ;    
 53     for( int i = 1 ; i <= k ; i++ )
 54     {
 55         a = read( ) , b = read( ) ;
 56         add( a + n , b , inf ) ;
 57         add( b , a + n , 0 ) ;
 58     }
 59 }
 60 
 61 
 62 bool bfs( ) 
 63 {
 64     memset( dis , -1 , sizeof(dis) ) ;
 65     dis[s] = 0 ; Q.push( s ) ;
 66     while( !Q.empty( ) )
 67     {
 68         int u = Q.front( ) ; Q.pop( ) ;
 69         for( int i = head[u] ; ~i ; i = edge[i].nxt )
 70         {
 71             int v = edge[i].to ;
 72             if( dis[v] < 0 && edge[i].vi > 0 )
 73             {
 74                 dis[v] = dis[u] + 1 ;
 75                 Q.push( v ) ;
 76             }
 77         }
 78     }
 79 //    cout<<endl;
 80     return dis[t] > 0 ;
 81 }
 82 
 83 
 84 long long int dfs( int u , long long int tmp )
 85 {
 86     if( u == t ) return tmp ;
 87     long long int an = 0ll , cost = 0ll ;
 88     for( int i = cur[u] ; ~i ; i = edge[i].nxt )
 89     {
 90         int  v = edge[i].to ;
 91         if( dis[v] != dis[u] + 1 ) continue ;
 92         an = dfs( v , min( tmp - cost , (long long )edge[i].vi ) ) ;
 93         edge[i].vi -= an , edge[i^1].vi += an ; cost += an;
 94         if( edge[i].vi ) cur[u] = i ; 
 95         if( cost == tmp ) return cost ;
 96     }
 97     if( !cost ) dis[u] = -1;
 98     return cost ;
 99 }
100 
101 void sov( )
102 {
103     long long int ans = 0 ;
104     while( bfs( ) ) 
105     {
106         for( int x = 1 ; x <= n<<1 ; ++x ) cur[x] = head[x] ;
107         head[s] = cur[s] ;
108         ans += dfs( s , (long long )inf ) ;
109     }
110     printf( "%d" , min( ans , (long long)m ) ) ;
111     return ;
112 }
113 
114 
115 int main( )
116 {
117 //    Init( ) ;
118     input( ) ;
119     sov( ) ;
120 //    fclose( stdin ) ;
121 //    fclose( stdout ) ;
122     return 0 ;
123 }