Cod sursa(job #1754003)

Utilizator LucianTLucian Trepteanu LucianT Data 7 septembrie 2016 14:07:55
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <bits/stdc++.h>
#define maxN 205
#define INF (1<<30)
using namespace std;
queue<int>Que;
bool seen[maxN];
int t[maxN],nod;
int n,i,j,x,y,maxflow,addflow;
int cap[maxN][maxN],flow[maxN][maxN];
bool bfs()
{
    while(!Que.empty())
        Que.pop();
    memset(seen,false,sizeof(seen));
    Que.push(0);
    seen[0]=true;
    while(!Que.empty())
    {
        int node=Que.front();
        Que.pop();
        for(i=1;i<=2*n+1;i++)
        {
            if(cap[node][i]==flow[node][i] || seen[i])
                continue;
            seen[i]=true;
            Que.push(i);
            t[i]=node;
            if(i == 2*n+1)
                return true;
        }
    }
    return false;
}
int main()
{
    freopen("harta.in","r",stdin);
    freopen("harta.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d %d",&cap[0][i],&cap[i+n][2*n+1]);
        for(j=1;j<=n;j++)
            if(i!=j)
                cap[i][j+n]=1;
    }
    while(bfs())
    {
        addflow=INF;
        for(nod=2*n+1;nod;nod=t[nod])
            if(addflow>cap[t[nod]][nod]-flow[t[nod]][nod])
                addflow=cap[t[nod]][nod]-flow[t[nod]][nod];
        for(nod=2*n+1;nod;nod=t[nod])
            flow[t[nod]][nod]+=addflow,
            flow[nod][t[nod]]-=addflow;
        maxflow+=addflow;
    }
    printf("%d\n",maxflow);
    for(i=1;i<=n;i++)
        for(j=n+1;j<=2*n;j++)
            if(flow[i][j]==1)
                printf("%d %d\n",i,j-n);
    return 0;
}