最大流加强 dinic+当前弧优化

qyy开始练习网络流啦，啊，蒟蒻只会套版，很裸的题，我连题都不想发了，可以参考我的代码（虽然我也是看的别人的

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

重新贴板，和上面的程序几乎没什么区别，码风固定了，值得开心。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <queue>
 5 const int N = 1003, M = 3e5 + 7, inf = 1 << 30;
 6 using namespace std;
 7 int n, m, head[N], cnt, dis[N],cur[N];
 8 queue<int>Q;
 9 struct edge
10 {
11     int nxt,to,vi;
12 } E[M<<1];
13 
14 void add(int u,int v,int vi)
15 {
16     E[++cnt] = (edge){head[u],v,vi}; head[u] = cnt;
17     E[++cnt] = (edge){head[v],u,0}; head[v] = cnt;
18 }
19 
20 void Init()
21 {
22     scanf("%d%d",&n,&m); cnt = -1;
23     int u,v,vi;
24     memset(head,-1,sizeof(head));
25     for(int i = 1; i <= m; ++i)
26     {    
27         scanf("%d%d%d",&u,&v,&vi);
28         add(u,v,vi);
29     }
30 }
31 
32 bool bfs()
33 {
34     memset(dis,-1,sizeof(dis));
35     Q.push(1); dis[1] = 0;
36     while(!Q.empty())
37     {
38         int u =  Q.front(); Q.pop();
39         for(int i = head[u]; ~i; i = E[i].nxt)
40         {
41             int v = E[i].to;
42             if(dis[v] == -1 && E[i].vi > 0) dis[v] = dis[u] + 1, Q.push(v);
43         }
44     }
45     return (dis[n] > 0);
46 }
47 
48 int dfs(int u,int t,int ff)
49 {
50     int ret = 0, cost = 0;
51     if(u == t) return ff;
52     for(int i = cur[u] ; ~i; i = E[i].nxt)
53     {
54         int v = E[i].to;
55         if(dis[v] != dis[u] + 1) continue;
56         cost = dfs(v,t,min(ff-ret,E[i].vi));
57         E[i].vi -= cost, E[i^1].vi += cost; ret += cost;
58         if(E[i].vi) cur[u] = i;
59         if(ret == ff) return ff;
60     }
61     if(!ret) dis[u] = -1;
62     return ret;
63 }
64 
65 int max_flow(int s,int t)
66 {
67     int ret = 0;
68     while(bfs())
69     {
70         for(int i = 1; i <= n; ++i) cur[i] = head[i];
71         ret += dfs(s,t,inf);
72     }
73     return ret;
74 }
75 
76 void Solve()
77 {
78     int ans = max_flow(1,n);
79     printf("%d
",ans);
80 }
81 
82 int main()
83 {
84     Init();
85     Solve();
86     
87     return 0;
88 }