FLOW1 - Giao lưu

Tác giả: hieult

Ngôn ngữ: C++

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<sstream>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00001
#define oo 111111111
#define mod 1000000007
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, x) memset(a, x, sizeof(a))
#define SZ(a) (int)(a.size())
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
typedef long long ll;

// Dinic

void OPEN(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
}

#define maxn 1311
#define maxe (1 << 20)

struct Dinic{
    int s, t, E, adj[maxe], cap[maxe], flow[maxe], next[maxe],
    last[maxn], que[maxn], level[maxn], run[maxn];
    
    void init(int _s, int _t){
        s = _s; t = _t; E = 0;
        memset(last, -1, sizeof(last));
    }
    
    void add(int u, int v, int c1, int c2){
        adj[E] = v; cap[E] = c1; flow[E] = 0; next[E] = last[u]; last[u] = E++;
        adj[E] = u; cap[E] = c2; flow[E] = 0; next[E] = last[v]; last[v] = E++;
    }
    
    bool bfs(){
        memset(level, -1, sizeof(level));
        level[s] = 0;
        int size = 0; que[size++] = s;
        rep(i, size){
            for(int u = que[i], e = last[u]; e != -1; e = next[e]){
                int v = adj[e];
                if(level[v] == -1 && flow[e] < cap[e]){
                    level[v] = level[u] + 1;
                    que[size++] = v;
                }
            }
        }
        return level[t] != -1;
    }
    
    int dfs(int u, int bot){
        if(u == t) return bot;
        for(int &e = run[u]; e != -1; e = next[e]){
            int v = adj[e], delta;
            if(level[v] == level[u] + 1 && flow[e] < cap[e] && (delta = dfs(v, min(bot, cap[e] - flow[e]))) > 0){
                flow[e] += delta;
                flow[e ^ 1] -= delta;
                return delta;
            }
        }
        return 0;
    }
    
    ll maxflow(){
        ll total = 0;
        while(bfs()){
            memcpy(run, last, sizeof(last));
            for(int delta = dfs(s, oo); delta > 0; delta = dfs(s, oo)) total += delta;
        }
        return total;
    }
    
}dinic;

int n, m, x;
char s[11111];
vector<pair<int, int> > V1[300], V2[300];

int main(){
    //OPEN();
    scanf("%d %d\n", &n, &m);
    dinic.init(0, 2 * n + 2 * m + 1);
    FOR(i, 1, m) dinic.add(n + i, n + m + i, 1, 0);
    FOR(i, 1, n) dinic.add(0, i, 1, 0);
    FOR(i, 1, n) dinic.add(n + m + m + i, n + n + m + m + 1, 1, 0);
    FOR(i, 1, n){
        gets(s);
        istringstream iss(s);
        while(iss >> x){
            V1[x].PB(MP(dinic.E, i));
            dinic.add(i, n + x, 1, 0);
        }
    }
    
    FOR(i, 1, n){
        gets(s);
        istringstream iss(s);
        while(iss >> x){
            V2[x].PB(MP(dinic.E, i));
            dinic.add(n + m + x, n + m + m + i, 1, 0);
        }
    }
    
   // printf("%lld\n",dinic.maxflow());
    dinic.maxflow();
    
    FOR(i, 1, m){
        int t1 = 0, t2 = 0;
        rep(j, SZ(V1[i])) if(dinic.flow[V1[i][j].fi]) t1 = V1[i][j].se;
        rep(j, SZ(V2[i])) if(dinic.flow[V2[i][j].fi]) t2 = V2[i][j].se;
        printf("%d %d\n",t1,t2);
    }
}

Download