Pagini recente » Cod sursa (job #3128338) | Cod sursa (job #2643102) | Cod sursa (job #343401) | Cod sursa (job #2643077) | Cod sursa (job #3187271)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
int N,M,k,x,parent[202],dst,cap[202][202],flow[202][202],in,out;
bool visited[202];
ifstream f ("harta.in");
ofstream g ("harta.out");
void bfs()
{
for(int i=1;i<=2*N+1;i++)
{
parent[i]=-1; //indicele copilului
visited[i]=false;
}
queue <int> q;
q.push(0);
visited[0]=true;
parent[0]=-1;
while(!q.empty())
{
int k=q.front();
q.pop();
if(k!=dst)
{
if(k>=1 && k<=N)
{
for(int i=N+1;i<=2*N;i++)
if(!visited[i] && cap[k][i]!=flow[k][i])
{
visited[i]=true;
parent[i]=k;
q.push(i);
}
}
else
{
for(int i=1;i<=N;i++)
if(!visited[i] && cap[k][i]!=flow[k][i])
{
visited[i]=true;
parent[i]=k;
q.push(i);
}
if(k!=0 && !visited[dst] && cap[k][dst]!=flow[k][dst])
{
visited[dst]=true;
parent[dst]=k;
q.push(dst);
}
}
}
}
}
int ford()
{
int maxflow=0;
bfs();
while(visited[dst])
{
for(int i=N+1;i<=2*N;i++)
{
if(visited[i] && cap[i][dst]!=flow[i][dst])
{
parent[dst]=i;
int minflow=100000,poz=dst;
while(poz)
{
minflow=min(minflow,cap[parent[poz]][poz]-flow[parent[poz]][poz]);
poz=parent[poz];
}
if(minflow!=0)
{
maxflow+=minflow;
poz=dst;
while(poz)
{
flow[parent[poz]][poz]+=minflow;
flow[poz][parent[poz]]-=minflow;
poz=parent[poz];
}
}
}
}
bfs();
}
return maxflow;
}
int main()
{
f>>N;
dst=2*N+1;
for(int i=1;i<=N;i++)
{
f>>out>>in;
M+=out;
cap[0][i]=out;
cap[i+N][dst]=in;
}
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
if(j!=i)
cap[i][j+N]=1;
g<<ford()<<'\n';
for(int i=1;i<=N;i++)
for(int j=N+1;j<=2*N;j++)
if(flow[i][j])
g<<i<<' '<<j-N<<'\n';
f.close();
g.close();
return 0;
}