Pagini recente » Cod sursa (job #359739) | Cod sursa (job #97149) | Cod sursa (job #686362) | Cod sursa (job #2574977) | Cod sursa (job #2680632)
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define inf 1000000000
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
const int NMAX=100;
int cap[2*NMAX+5][2*NMAX+5];
int n;
vector<int> adj[2*NMAX+5];
int source,dest,ant[2*NMAX+5];
bool bfs(int node)
{
queue<int> q;
vector<bool> viz(n+5,0);
q.push(node);
viz[node]=1;
ant[node]=-1;
while(!q.empty())
{
int crt=q.front();
// cout<<crt<<" ";
if(crt==dest) return 1;
for(auto x:adj[crt])
{
if(viz[x]==0)
{
if(cap[crt][x]>0)
{
viz[x]=1;
q.push(x);
ant[x]=crt;
//cout<<x<<" ";
if(x==dest)
{
return 1;
}
}
}
}
q.pop();
}
return 0;
}
int flow(int node,int flw)
{
if(flw==0) return 0;
while(node!=source)
{
flw=min(flw,cap[ant[node]][node]);
node=ant[node];
if(flw==0) return 0;
}
node=dest;
while(node!=source)
{
cap[ant[node]][node]-=flw;
cap[node][ant[node]]+=flw;
node=ant[node];
}
return flw;
}
int main()
{
f>>n;
for(int i=1;i<=n;i++)
{
int x,y;
f>>x>>y;
adj[0].pb(i);
adj[i].pb(0);
adj[i+n].pb(2*n+1);
adj[2*n+1].pb(i+n);
cap[0][i]=x;
cap[i+n][2*n+1]=y;
}
for(int i=1;i<=n;i++)
{
for(int j=n+1;j<=2*n;j++)
{
if(i+n!=j){
cap[i][j]=1;
adj[i].pb(j);
adj[j].pb(i);
}
}
}
source=0;
dest=2*n+1;
int sol=0;
while(bfs(source))
{
sol+=flow(dest,1e9);
//cout<<0;
}
g<<sol<<'\n';
for(int i=1;i<=n;i++)
{
for(int j=n+1;j<=2*n;j++)
{
if(i+n!=j&&cap[i][j]==0)
{
g<<i<<" "<<j-n<<'\n';
}
}
}
}