Cod sursa(job #1868615)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 5 februarie 2017 01:21:20
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include<bits/stdc++.h>
#define maxN 205
using namespace std;
int s,d;
deque<int> q;
vector<pair<int,int> > sol;
bool seen[maxN];
vector<int> v[maxN];
int c[maxN][maxN],f[maxN][maxN],tt[maxN],n,x,y,flux;
bool bfs()
{
    for(int i=s;i<=d;i++) seen[i]=0;
    q.push_back(0);
    seen[0]=1;
    while(!q.empty())
    {
        int nod=q.front();
            for(vector<int>::iterator it=v[nod].begin();it!=v[nod].end();it++)
        {
            if(!seen[*it] && c[nod][*it]>f[nod][*it])
            {
                seen[*it]=1;
                q.push_back(*it);
                tt[*it]=nod;
            }
        }
        q.pop_front();
    }
    return seen[d];
}
int main()
{
    freopen("harta.in","r",stdin);
    freopen("harta.out","w",stdout);
    scanf("%d",&n);
    s=0;
    d=2*n+1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        c[s][i]=x;
        c[i+n][d]=y;
        v[s].push_back(i);
        v[i].push_back(s);
        v[i+n].push_back(d);
        v[d].push_back(i+n);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i!=j)
            {
                c[i][j+n]=1;
                v[i].push_back(j+n);
                v[j+n].push_back(i);
            }
        }
    }
    while(bfs())
    {
        for(vector<int>::iterator it=v[d].begin();it!=v[d].end();it++)
        {
            flux=c[*it][d]-f[*it][d];
            for(int t=*it;t>0;t=tt[t])
            {
                flux=min(flux,c[tt[t]][t]-f[tt[t]][t]);
            }
            f[*it][d]+=flux;
            f[d][*it]-=flux;
            for(int t=*it;t>0;t=tt[t])
            {
                f[tt[t]][t]+=flux;
                f[t][tt[t]]-=flux;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            if(i!=j && f[i][j+n]==1) sol.push_back({i,j});
    }
    printf("%d\n",sol.size());
    for(vector<pair<int,int> >::iterator it=sol.begin();it!=sol.end();it++)
    {
        printf("%d %d\n",(*it).first,(*it).second);
    }
    return 0;
}