Cod sursa(job #2008346)

Utilizator victoreVictor Popa victore Data 6 august 2017 12:30:47
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>

#define pb(x) push_back(x)

using namespace std;

const int nmax=3*105;

vector<int> g[nmax],sol[105];
int tata[nmax],cap[nmax][nmax],flux[nmax][nmax];
int n;

inline bool bfs()
{
    queue<int> q;
    memset(tata,-1,sizeof(tata));
    int i;
    q.push(0);
    int node,cnode;
    while(!q.empty())
    {
        node=q.front();
        q.pop();
        if(node==(n<<1|1))
            return 1;
        for(i=0;i<g[node].size();++i)
        {
            cnode=g[node][i];
            if(tata[cnode] == -1 && cap[node][cnode] > flux[node][cnode])
            {
                tata[cnode]=node;
                q.push(cnode);
            }
        }
    }
    return 0;
}


int main()
{
    freopen("harta.in","r",stdin);
    freopen("harta.out","w",stdout);
    int x,y,i,j;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
    {
        scanf("%d%d",&x,&y);
        cap[0][i]=x;
        g[0].pb(i);
        g[i].pb(0);
        cap[n+i][(n<<1)|1]=y;
        g[n+i].pb((n<<1)|1);
        g[(n<<1)|1].pb(n+i);
    }
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            if(i!=j)
                g[i].pb(n+j),g[n+j].pb(i),cap[i][n+j]++;
    int cnode,cflux;
    while(bfs())
    {
        for(i=0;i<g[(n<<1)|1].size();++i)
        {
            cnode=g[n<<1|1][i];
            if(tata[cnode] == -1 || cap[cnode][(n<<1)+1] == flux[cnode][(n<<1)|1])
                continue;
            tata[n<<1|1]=cnode;
            cflux=2e9;
            for(j=(n<<1|1);j;j=tata[j])
                cflux=min(cflux,cap[tata[j]][j] - flux[tata[j]][j]);
            for(j=(n<<1|1);j;j=tata[j])
            {
                flux[tata[j]][j]+=cflux;
                flux[j][tata[j]]-=cflux;
            }
        }
    }
    int cnt=0;
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            if(i!=j && flux[i][n+j])
                sol[i].pb(j),++cnt;
    printf("%d\n",cnt);
    for(i=1;i<=n;++i)
        for(j=0;j<sol[i].size();++j)
            printf("%d %d\n",i,sol[i][j]);
}