Pagini recente » Cod sursa (job #1263665) | Cod sursa (job #1699022) | Cod sursa (job #3130036) | Cod sursa (job #481721) | Cod sursa (job #3193716)
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n, src, dst;
vector<int>G[2*N];
vector<bool>vizitat;
ifstream f("harta.in");
ofstream g("harta.out");
int capacitate[2*N][2*N],flow[2*N][2*N],t[2*N];
void bfs()
{
vizitat.assign(dst + 1, false);
queue<int> q;
q.push(src);
vizitat[src]=true;
t[src]=0;
while(!q.empty())
{
int current=q.front();
q.pop();
if(current == dst)
continue;
for(int next:G[current])
{
if(!vizitat[next] && capacitate[current][next]!=flow[current][next])
{
vizitat[next]=true;
t[next]=current;
q.push(next);
}
}
}
}
int main()
{
f >> n;
src=0;
dst=2*n+1;
int totalMuchii = 0;
for(int i=1;i<=n;i++)
{
int x,y;
f >> x >> y;
totalMuchii+=y;
capacitate[src][i]=x;
capacitate[n+i][dst]=y;
G[src].push_back(i);
G[i].push_back(src);
G[n+i].push_back(dst);
G[dst].push_back(n+i);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j)
{
capacitate[i][n+j]=1;
G[i].push_back(n+j);
G[n+j].push_back(i);
}
}
}
while(1)
{
bfs();
if(vizitat[dst]==false) break;
for(int next:G[dst])
{
if(vizitat[next]==false || capacitate[next][dst]==flow[next][dst])
continue;
t[dst]=next;
int minFlow=INT_MAX;
for(int nod=dst;nod!=src;nod=t[nod])
minFlow=min(minFlow,capacitate[t[nod]][nod]-flow[t[nod]][nod]);
if(minFlow==0)
continue;
for(int nod=dst;nod!=src;nod=t[nod])
{
flow[t[nod]][nod] += minFlow;
flow[nod][t[nod]] -= minFlow;
}
}
}
g << totalMuchii;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j && capacitate[i][n + j]==flow[i][n + j])
g << i << " " << j <<endl;
}
}
return 0;
}