Pagini recente » Cod sursa (job #2800021) | Cod sursa (job #1157975) | Cod sursa (job #1328413) | Cod sursa (job #866559) | Cod sursa (job #2959961)
#include <bits/stdc++.h>
#define maXX 22000
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector<int> adj[6001];
int MaxFLOW,flow,fluxmin,fluxmax;
int i,j,k,n,m,C[6001][6001],viz[6001],x,y,z,fth[6001],nod,F[6001][6001],e,source,last_node;
queue<int>q;
int bfs()
{
int top,next;
memset(viz,0,sizeof(viz));
q.push(source);
while(q.empty() == false)
{
top = q.front();
q.pop();
viz[top] = 1;
if(top == 2*n+1)
break;
for(int i=0; i<adj[top].size(); i++)
{
next = adj[top][i];
if(viz[next] == 0 && F[top][next] != C[top][next])
{
viz[next]=1;
q.push(next);
fth[next] = top;
}
}
}
return viz[n];
}
int main()
{
f>>n;
last_node = 2*n+1;
source = 0;
for(int i=1;i<=n;i++)
{
f>>x>>y;
adj[source].push_back(i);
adj[i].push_back(source);
adj[last_node].push_back(n+i);
adj[n+i].push_back(last_node);
C[0][i] = x;
C[i+n][2*n+1] = y;
}
for(int i=1;i<=n;i++)
{
for(int j=1+n;j<=2*n;j++)
{
if(i!=j-n)
{
C[i][j] = 1;
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
for(MaxFLOW = 0; bfs();)
{
for(i=0; i<adj[last_node].size(); i++)
{
fluxmin = 10e7;
nod = adj[last_node][i];
if(!viz[nod] || F[nod][last_node] == C[nod][last_node])
continue;
fth[last_node] = nod;
for(nod = last_node; nod != source ; nod = fth[nod])
{
fluxmin = min(fluxmin,C[fth[nod]][nod] - F[fth[nod]][nod]);
}
if(fluxmin == 0)
continue;
for (nod = last_node; nod != source ; nod = fth[nod])
{
F[fth[nod]][nod] += fluxmin;
F[nod][fth[nod]] -= fluxmin;
}
MaxFLOW += fluxmin;
}
// MaxFLOW += fluxmin;
}
g<<MaxFLOW<<'\n';
for(i=1;i<=n;i++)
{
for(j=0;j<adj[i].size();j++)
{
if(adj[i][j] !=0 && F[i][adj[i][j]])
g<<i<<" "<<adj[i][j]-n<<'\n';
}
}
return 0;
}