Cod sursa(job #984667)

Utilizator gbi250Gabriela Moldovan gbi250 Data 15 august 2013 00:53:57
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#define pb push_back
#define NODES 220
#define inf 0x3f3f3f3f
using namespace std;

int n, source, sink, capacity[NODES][NODES], f[NODES][NODES], p[NODES], edges;
bool visited[NODES];
queue <int> q;
vector <int> adj[NODES];


inline void read()
{
    freopen("harta.in", "r", stdin);
    int x, y;
    scanf("%d", &n);
    source=2*n+1; sink=2*n+2;
    for(int i=1;i<=n;++i)
    {
        scanf("%d %d", &x, &y);
        edges+=x;
        adj[source].pb(i); adj[i].pb(source); capacity[source][i]=x;
        adj[i+n].pb(sink); adj[sink].pb(i+n); capacity[i+n][sink]=y;
        for(int j=1;j<=n;++j)
            if(i!=j)
            {
                adj[i].pb(j+n); adj[j+n].pb(i);
                capacity[i][j+n]=1;
            }
    }
}

inline void write()
{
    freopen("harta.out", "w", stdout);
    printf("%d\n", edges);
    for(int i=1;i<=n;++i)
        for(int j=n+1;j<=2*n;++j)
            if(f[i][j])
                printf("%d %d\n", i, j-n);
}

inline bool BFS()
{
    memset(visited, 0, sizeof(visited));
    q.push(source); visited[source]=1;

    while(!q.empty())
    {
        int node=q.front(); q.pop();
        if(node==sink)
            continue;
        for(vector <int> :: iterator it=adj[node].begin(); it!=adj[node].end(); ++it)
            if(!visited[*it] && capacity[node][*it] > f[node][*it])
            {
                visited[*it]=1;
                p[*it]=node;
                q.push(*it);
            }
    }
    return visited[sink];
}

inline void solve()
{
    int min_flow, node;
    while(BFS())
        for(vector <int> :: iterator it=adj[sink].begin(); it!=adj[sink].end(); ++it)
        {
            p[sink]=*it;
            min_flow=inf;
            for(int i=sink; i!=source; i=p[i])
                min_flow=min(min_flow, capacity[p[i]][i]-f[p[i]][i]);
            for(int i=sink; i!=source; i=p[i])
            {
                f[p[i]][i]+=min_flow;
                f[i][p[i]]-=min_flow;
            }
        }
}

int main()
{
    read();
    solve();
    write();
    return 0;
}