Pagini recente » Cod sursa (job #2562304) | Cod sursa (job #986480)
Cod sursa(job #986480)
#include<fstream>
#include<cstring>
using namespace std;
typedef struct celula{
int nod;
celula *next;
}*lista;
lista graf[205],v;
int cost[205][205],i,j,n,m,x,y,tata[205],coada[2005],s,d,sol;
bool ok,viz[205];
void update(){
int flow=1000,aux=d;
while (tata[aux]!=aux) { flow=min(flow,cost[tata[aux]][aux]); aux=tata[aux]; }
aux=d;
while (tata[aux]!=aux) { cost[tata[aux]][aux]-=flow; cost[aux][tata[aux]]+=flow; aux=tata[aux]; }
}
void bfs(){
int begin,end,i; ok=0;
begin=end=1; coada[1]=0; memset(viz,0,sizeof(viz)); memset(tata,0,sizeof(tata)); viz[0]=1;
while (begin<=end) {
int nod=coada[begin];
for (lista p=graf[nod]; p; p=p->next)
if (viz[p->nod]==0&&cost[nod][p->nod]>0) {
tata[p->nod]=nod;
if (p->nod==d) { ok=1; update(); }
else { ++end; coada[end]=p->nod; viz[p->nod]=1; }
}
++begin;
}
}
void muchie(int x, int y) {
v=new celula; v->nod=y; v->next=graf[x]; graf[x]=v;
v=new celula; v->nod=x; v->next=graf[y]; graf[y]=v; }
int main(void){
ifstream fin("harta.in");
ofstream fout("harta.out");
fin>>n; d=2*n+1; s=0;
for (i=1; i<=n; ++i) {
fin>>x>>y; m+=x; cost[s][i]=x; cost[n+i][d]=y; muchie(s,i); muchie(n+i,d);
for (j=1; j<=n; ++j)
if (j!=i){ cost[i][n+j]=1; muchie(i,n+j); }
}
fout<<m<<"\n"; ok=1;
while (ok) bfs();
for (i=1; i<=n; ++i)
for (j=1; j<=n; ++j)
if (cost[i][n+j]==0&&i!=j) fout<<i<<" "<<j<<"\n";
return(0);
}