BAOVE - Bảo vệ

Tác giả: skyvn97

Ngôn ngữ: C++

#include<bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
using namespace std;
const int INF=(int)1e9+7;
class DinicFlow {
    private:
    vector<int> dist,head,q,work;
    vector<int> capa,flow,next,point;
    int n,m;
    public:
    DinicFlow() {
        n=0;m=0;
    }
    DinicFlow(int n) {
        this->n=n;
        this->m=0;
        dist=vector<int>(n+7);
        head=vector<int>(n+7,-1);
        q=vector<int>(n+7);
        work=vector<int>(n+7);
    }
    void addedge(int u,int v,int c1,int c2) {
        point.push_back(v);capa.push_back(c1);flow.push_back(0);next.push_back(head[u]);head[u]=m;m++;
        point.push_back(u);capa.push_back(c2);flow.push_back(0);next.push_back(head[v]);head[v]=m;m++;
    }
    bool bfs(int s,int t) {
        FOR(i,1,n) dist[i]=-1;
        int sz=1;
        q[0]=s;dist[s]=0;
        REP(x,sz) {
            int u=q[x];
            for (int i=head[u];i>=0;i=next[i])
                if (dist[point[i]]<0 && flow[i]<capa[i]) {
                    dist[point[i]]=dist[u]+1;
                    q[sz]=point[i];
                    sz++;
                }
        }
        return (dist[t]>=0);
    }
    int dfs(int s,int t,int f) {
        if (s==t) return (f);
        for (int &i=work[s];i>=0;i=next[i])
            if (dist[point[i]]==dist[s]+1 && flow[i]<capa[i]) {
                int d=dfs(point[i],t,min(f,capa[i]-flow[i]));
                if (d>0) {
                    flow[i]+=d;
                    flow[i^1]-=d;
                    return (d);
                }
            }
        return (0);
    }
    int maxflow(int s,int t) {
        int totflow=0;
        while (bfs(s,t)) {
            FOR(i,1,n) work[i]=head[i];
            while (true) {
                int d=dfs(s,t,INF);
                if (d<=0) break;
                totflow+=d;
            }
        }
        return (totflow);
    }
};
int n;
DinicFlow G;
void process(void) {
    scanf("%d",&n);
    G=DinicFlow(n);
    int u,v,d;
    while (scanf("%d%d%d",&u,&v,&d)==3) G.addedge(u,v,d,0);
    cerr << 123 << endl;
    printf("%d",G.maxflow(n,1));
}
int main(void) {
#ifndef ONLINE_JUDGE
    freopen("tmp.txt","r",stdin);
#endif
    process();
    return 0;
}

Download