Cod sursa(job #2680760)

Utilizator AndreiStanescuAlloys Nokito AndreiStanescu Data 4 decembrie 2020 12:28:45
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.31 kb
#include<bits/stdc++.h>
#define pii pair<int,int>
#define Dim 1000000000
#define N 210
using namespace std;
vector <int> G[N];
queue <int> q;
int n,m,C[N][N],pred[N],f[N][N];
int source,sink;
bool viz[N];
	
void read()
{
    int i,x,y;
    freopen("harta.in","r",stdin);
    scanf("%d",&n);
    source=0;
    sink=2*n+1;
    for(i=1;i<=n;i++)
    {
        scanf("%d %d",&x,&y);
        G[source].emplace_back(i);
        G[i].emplace_back(source);
        C[source][i]=x;
        G[i+n].emplace_back(sink);
        G[sink].emplace_back(i+n);
        C[i+n][sink]=y;
    }
    for(int i=1;i<=n;++i)
        for(int j=n+1;j<=2*n;++j){
            if(i+n != j){
                G[i].emplace_back(j);
                G[j].emplace_back(i);
                C[i][j] = 1;
            }
        }
}
	

bool bfs()
{
    memset(viz,0,sizeof(viz));
    q.push(source);
    viz[source] = 1;
    while(!q.empty())
    {
        int nod = q.front();
        q.pop();
        if(nod == sink)
            continue;
        for(auto& i:G[nod])
        {
            if(viz[i] || f[nod][i] == C[nod][i])
                continue;
            viz[i] = 1;
            q.push(i);
            pred[i] = nod;
        }
    }
    return viz[sink];
}
	
	
int Edmond()
{
    int flow,i,f_min,nod,pj;
    for(flow = 0; bfs() ;){
        for(auto& i:G[sink])
        {
            if(!viz[i] || f[i][sink] == C[i][sink])
                continue;
            pred[sink] = i;
            nod = sink;
            f_min = Dim;
            while(nod != source)
            {
                f_min = min(f_min, C[pred[nod]][nod] - f[pred[nod]][nod]);
                nod = pred[nod];
            }
            if(!f_min)
                continue;
            //actualizare
            nod = sink;
            while(nod != source)
            {
                f[pred[nod]][nod] += f_min;
                f[nod][pred[nod]] -= f_min;
                nod = pred[nod];
            }
            flow += f_min;
        }
    }
    return flow;
}
	

	
int main()
{
    read();
    freopen("harta.out","w",stdout);
    cout<<Edmond()<<'\n';
    for(int i=1;i<=n;++i)
        for(int j=n+1;j<=2*n;++j){
            if(i+n != j && f[i][j] == C[i][j])
                cout<<i<<' '<<j-n<<'\n';
        }
}