Cod sursa(job #1019359)

Utilizator andrettiAndretti Naiden andretti Data 30 octombrie 2013 23:14:45
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#define pb push_back
#define maxn 205
#define inf 0x3f3f3f3f
using namespace std;

int n,m,nr,Flow;
int v[maxn],father[maxn],gi[maxn],ge[maxn];
int c[maxn][maxn],f[maxn][maxn];
vector<int> l[maxn];
int source,sink;

void read()
{
    scanf("%d",&n); sink=2*n+1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&c[source][i],&c[i+n][sink]);
        l[source].pb(i); l[i].pb(source);
        l[i+n].pb(sink); l[sink].pb(i+n);

        for(int j=1;j<=n;j++)
         if(i!=j)
         {
             l[j+n].pb(i); l[i].pb(j+n);
             c[i][j+n]=1;
         }
    }
}

int bfs()
{
    queue<int> q;
    int k;

    for(v[source]=nr,q.push(source);!q.empty();q.pop())
    {
        k=q.front();
        if(k==sink) continue;
        for(unsigned int i=0;i<l[k].size();i++)
         if(v[l[k][i]]!=nr && f[k][l[k][i]]<c[k][l[k][i]])
         {
             q.push(l[k][i]); v[l[k][i]]=nr;
             father[l[k][i]]=k;
         }
    }
    if(v[sink]==nr) return 1;
    return 0;
}

void solve()
{
    int Min;
    for(nr=1;bfs();)
    {
        for(unsigned int i=0;i<l[sink].size();i++)
         if(v[l[sink][i]]==nr && f[l[sink][i]][sink]<c[l[sink][i]][sink])
         {
             father[sink]=l[sink][i]; Min=inf;
             for(int j=sink;j!=source;j=father[j])
              Min=min(Min,c[father[j]][j]-f[father[j]][j]);

             for(int j=sink;j!=source;j=father[j])
             {
                 f[father[j]][j]+=Min;
                 f[j][father[j]]-=Min;
             }
             Flow+=Min;
         }
         nr++;
    }

    printf("%d\n",Flow);
}

void print()
{
    for(int i=1;i<=n;i++)
     for(int j=n+1;j<=2*n;j++)
      if(f[i][j]==1)
       printf("%d %d\n",i,j-n);
}

int main()
{
    freopen("harta.in","r",stdin);
    freopen("harta.out","w",stdout);

    read();
    solve();
    print();

    fclose(stdin);
    fclose(stdout);
    return 0;
}