Pagini recente » Borderou de evaluare (job #947250) | Cod sursa (job #2047545)
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int INF = 0x7fffffff;
FILE *fin = fopen("revolutie.in", "r");
FILE *fout = fopen("revolutie.out", "w");
int n;
int vizitat[400];
vector <int> muchie[400];
int c[400][400];
int tata[400];
int f[400][400];
int minim(int a, int b)
{
if(a<b) return a;
return b;
}
struct selectat
{
int x,y;
};
selectat v[400];
selectat raspunsuri[400];
int sortare(selectat a, selectat b)
{
if(a.x < b.x) return true;
return false;
}
int bfs()
{
for(int i=0;i<=2*n+1;i++)
{
vizitat[i]=0;
}
queue <int> frontiera;
frontiera.push(0);
vizitat[0]=1;
while(!frontiera.empty())
{
int nod = frontiera.front();
frontiera.pop();
if(nod == 2*n+1 ) continue;
for(auto m : muchie[nod])
{
if(c[nod][m] == f[nod][m] || vizitat[m]==1) continue;
tata[m] = nod;
vizitat[m]=1;
frontiera.push(m);
}
}
return vizitat[2*n+1];
}
int main()
{
fscanf(fin, "%d", &n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
int x;
fscanf(fin, "%d", &x);
if(x == 1) c[i][n+j]=1;
muchie[i].push_back(n+j);
muchie[n+j].push_back(i);
}
for(int i=1;i<=n;i++)
{
c[0][i] = 1;
c[n+i][2*n+1] = 1;
muchie[0].push_back(i);
muchie[i].push_back(0);
muchie[2*n+1].push_back(n+i);
muchie[n+i].push_back(2*n+1);
}
int fluxminim;
int flux=0;
while (bfs())
{
for(auto m : muchie[2*n+1])
{
if(c[m][2*n+1] == f[m][2*n+1] || vizitat[m]==0) continue;
tata[2*n+1] = m;
fluxminim = INF;
int nod = 2*n+1;
while(nod!=0)
{
fluxminim = minim (fluxminim, c[tata[nod]][nod] - f[tata[nod]][nod]);
nod = tata[nod];
}
if(fluxminim == 0) continue;
nod = 2*n+1;
while(nod!=0)
{
f[tata[nod]][nod] += fluxminim;
f[nod][tata[nod]] -= fluxminim;
nod = tata[nod];
}
flux += fluxminim;
}
}
int cnt=0;
int rez=0;
if(flux < n) fprintf(fout,"-1");
else
{
for(int i=1;i<=n;i++)
for(int j=n+1;j<=2*n;j++)
{
if(f[i][j] == 1)
{
cnt++;
v[cnt].x=i;
v[cnt].y=j-n;
}
}
sort(v+1,v+cnt+1,sortare);
for(int i=1;i<=cnt;i++)
{
if(v[i].y!=i)
{
rez++;
raspunsuri[rez].x = i;
raspunsuri[rez].y = v[i].y;
}
for(int j=1;j<=n;j++)
{
if(v[j].y==i)
{
v[j].y=v[i].y;
}
}
}
fprintf(fout, "%d\n", rez);
for(int i=1;i<=rez;i++)
{
fprintf(fout, "C %d %d\n", raspunsuri[i].x, raspunsuri[i].y);
}
}
return 0;
}