bzoj2039: [2009国家集训队]employ人员雇佣（最小割）

第一道最小割的题目啊，还不是很熟悉，慢慢消化吧。

学习这种建图的方式和题解链接https://blog.csdn.net/blackjack_/article/details/73607561

题解我就不写了，暂时还讲不出来。。。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1000 + 5;
const int inf = 0x3f3f3f3f;
struct edge{
    int to, w, next;
} ed[maxn*maxn*3];
int n, tot, head[maxn], d[maxn];
int s, maxflow, t = maxn-1;             //t的赋值 不要越界啊，一开始设成maxn 睿智了
inline void add( int u, int v, int w ){
    ed[++tot].to = v; ed[tot].w = w; ed[tot].next = head[u]; head[u] = tot;
    ed[++tot].to = u; ed[tot].w = 0; ed[tot].next = head[v]; head[v] = tot;
}

inline bool bfs(){
    memset( d, 0, sizeof(d) );
    queue<int> q;
    q.push(s); d[s] = 1;
    while( !q.empty() ){
        int x = q.front();
        q.pop();
        for( int i=head[x]; i!=-1; i=ed[i].next ){
            int y = ed[i].to;
            if( ed[i].w && !d[y] ){
                d[y] = d[x] + 1;
                q.push(y);
                if(y==t) return 1;
            }
        }
    }
    return 0;
}

inline int dfs( int x, int flow ){
    if( x==t ) return flow;
    int res = flow, k;
    for( int i=head[x]; i!=-1 && res; i=ed[i].next ){
        int y = ed[i].to;
        if( ed[i].w && d[y]==d[x]+1 ){
            k = dfs(y, min(res, ed[i].w));
            if( !k ) d[y] = 0;
            ed[i].w -= k;
            ed[i^1].w += k;
            res -= k;
        }
    }
    return flow-res;
}

inline void dinic(){
    int flow = 0;
    while( bfs() ) 
        maxflow += dfs(s, inf); 
}

int main(){
    // freopen("in.txt", "r", stdin);
    scanf("%d", &n);
    memset( head, -1, sizeof(head) );
    tot = 1;
    int sum = maxflow = s = 0;
    for( int i=1; i<=n; i++ ){
        int w;
        scanf("%d", &w);
        add( i, t, w );
    }
    for( int i=1; i<=n; i++ ){
        int tmp = 0;
        for( int j=1; j<=n; j++ ){
            int w;
            scanf("%d", &w);
            add( i, j, w<<1 );
            tmp += w;
        }
        sum += tmp; add( s, i, tmp );
    }
    dinic();
    printf("%d
", sum-maxflow);

    return 0;
}