Cod sursa(job #1723889)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 1 iulie 2016 19:06:25
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include<cstdio>
#include<cstring>
#define MAXN 210
#define INF 100000000
using namespace std;
int capacity[MAXN][MAXN],flow[MAXN][MAXN],seen[MAXN],dad[MAXN],Queue[MAXN];
int source,sink;
int minimum(int a,int b){
    if(a<b)
        return a;
    return b;
}
bool BFS(){
    int left=1,right=1,i,node;
    memset(seen,0,sizeof(seen));
    Queue[left]=source;
    seen[source]=1;
    while(left<=right){
        node=Queue[left];
        left++;
        if(node==sink)
            continue;
        for(i=1;i<=sink;i++)
            if(seen[i]==0&&capacity[node][i]!=flow[node][i]){
                seen[i]=1;
                right++;
                Queue[right]=i;
                dad[i]=node;
            }
    }
    if(seen[sink]==1)
        return true;
    return false;
}
int main(){
    freopen("harta.in","r",stdin);
    freopen("harta.out","w",stdout);
    int n,i,j,k,add,node,edges=0;
    scanf("%d",&n);
    source=0;
    sink=2*n+1;
    for(i=1;i<=n;i++){
        scanf("%d%d",&capacity[source][i],&capacity[i+n][sink]);
        for(j=1;j<=n;j++)
            if(i!=j)
                capacity[i][j+n]=1;
    }
    while(BFS()==true)
        for(i=0;i<=2*n;i++)
            if(seen[i]==1&&capacity[i][sink]!=flow[i][sink]){
                dad[sink]=i;
                add=INF;
                for(node=sink;node!=source;node=dad[node])
                    add=minimum(add,capacity[dad[node]][node]-flow[dad[node]][node]);
                for(node=sink;node!=source;node=dad[node]){
                    flow[dad[node]][node]+=add;
                    flow[node][dad[node]]-=add;
                }
                edges+=add;
            }
    printf("%d\n",edges);
    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;
}