Pagini recente » Cod sursa (job #193286) | Cod sursa (job #1990694) | Cod sursa (job #674077) | Cod sursa (job #1952727) | Cod sursa (job #1019359)
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#define pb push_back
#define maxn 205
#define inf 0x3f3f3f3f
using namespace std;
int n,m,nr,Flow;
int v[maxn],father[maxn],gi[maxn],ge[maxn];
int c[maxn][maxn],f[maxn][maxn];
vector<int> l[maxn];
int source,sink;
void read()
{
scanf("%d",&n); sink=2*n+1;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&c[source][i],&c[i+n][sink]);
l[source].pb(i); l[i].pb(source);
l[i+n].pb(sink); l[sink].pb(i+n);
for(int j=1;j<=n;j++)
if(i!=j)
{
l[j+n].pb(i); l[i].pb(j+n);
c[i][j+n]=1;
}
}
}
int bfs()
{
queue<int> q;
int k;
for(v[source]=nr,q.push(source);!q.empty();q.pop())
{
k=q.front();
if(k==sink) continue;
for(unsigned int i=0;i<l[k].size();i++)
if(v[l[k][i]]!=nr && f[k][l[k][i]]<c[k][l[k][i]])
{
q.push(l[k][i]); v[l[k][i]]=nr;
father[l[k][i]]=k;
}
}
if(v[sink]==nr) return 1;
return 0;
}
void solve()
{
int Min;
for(nr=1;bfs();)
{
for(unsigned int i=0;i<l[sink].size();i++)
if(v[l[sink][i]]==nr && f[l[sink][i]][sink]<c[l[sink][i]][sink])
{
father[sink]=l[sink][i]; Min=inf;
for(int j=sink;j!=source;j=father[j])
Min=min(Min,c[father[j]][j]-f[father[j]][j]);
for(int j=sink;j!=source;j=father[j])
{
f[father[j]][j]+=Min;
f[j][father[j]]-=Min;
}
Flow+=Min;
}
nr++;
}
printf("%d\n",Flow);
}
void print()
{
for(int i=1;i<=n;i++)
for(int j=n+1;j<=2*n;j++)
if(f[i][j]==1)
printf("%d %d\n",i,j-n);
}
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
read();
solve();
print();
fclose(stdin);
fclose(stdout);
return 0;
}