Pagini recente » Rezultatele filtrării | Cod sursa (job #1418913) | Rezultatele filtrării | Rezultatele filtrării | Cod sursa (job #2008348)
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#define pb(x) push_back(x)
using namespace std;
const int nmax=3*105;
vector<int> g[nmax],sol[105];
int tata[nmax],cap[nmax][nmax],flux[nmax][nmax];
int n;
inline bool bfs()
{
queue<int> q;
memset(tata,-1,sizeof(tata));
int i;
q.push(0);
int node,cnode;
while(!q.empty())
{
node=q.front();
q.pop();
if(node==(n<<1|1))
return 1;
for(i=0;i<g[node].size();++i)
{
cnode=g[node][i];
if(tata[cnode] == -1 && cap[node][cnode] > flux[node][cnode])
{
tata[cnode]=node;
q.push(cnode);
}
}
}
return 0;
}
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
int x,y,i,j;
scanf("%d",&n);
for(i=1;i<=n;++i)
{
scanf("%d%d",&x,&y);
cap[0][i]=x;
g[0].pb(i);
g[i].pb(0);
cap[n+i][(n<<1)|1]=y;
g[n+i].pb((n<<1)|1);
g[(n<<1)|1].pb(n+i);
}
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
if(i!=j)
g[i].pb(n+j),g[n+j].pb(i),cap[i][n+j]++;
int cnode,cflux;
while(bfs())
{
for(i=0;i<g[(n<<1)|1].size();++i)
{
cnode=g[n<<1|1][i];
if(tata[cnode] == -1 || cap[cnode][(n<<1)+1] == flux[cnode][(n<<1)|1])
continue;
tata[n<<1|1]=cnode;
cflux=2e9;
for(j=(n<<1|1);j;j=tata[j])
cflux=min(cflux,cap[tata[j]][j] - flux[tata[j]][j]);
for(j=(n<<1|1);j;j=tata[j])
{
flux[tata[j]][j]+=cflux;
flux[j][tata[j]]-=cflux;
}
}
}
int cnt=0;
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
if(i!=j && flux[i][n+j])
sol[i].pb(j),++cnt;
printf("%d\n",cnt);
for(i=1;i<=n;++i)
for(j=0;j<sol[i].size();++j)
printf("%d %d\n",i,sol[i][j]);
}