Pagini recente » Monitorul de evaluare | algoritmiada-2019/runda-maraton/solutii/tubeyou | Cod sursa (job #2760249) | Arhiva de probleme | Cod sursa (job #1002948)
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
#define NM 210
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int N, i, j;
int S, D;
vector<int> G[NM];
vector< pair<int, int> > ANS;
int Cap[NM][NM], Flow[NM][NM];
int T[NM];
bool V[NM];
queue<int> Q;
bool BF ()
{
memset(V, 0, sizeof(V));
Q.push(S);
V[S]=1;
int node;
vector<int>::iterator it;
while (!Q.empty())
{
node=Q.front();
Q.pop();
if (node==D) continue;
for (it=G[node].begin(); it!=G[node].end(); ++it)
if (!V[*it] && Flow[node][*it]<Cap[node][*it])
{
V[*it]=1;
T[*it]=node;
Q.push(*it);
}
}
return V[D];
}
int main ()
{
f >> N;
S=0; D=2*N+1;
for (i=1; i<=N; i++)
{
G[S].push_back(i);
G[i].push_back(S);
G[D].push_back(i+N);
G[i+N].push_back(D);
f >> Cap[S][i] >> Cap[i+N][D];
for (j=1; j<=N; j++)
if (i!=j)
{
G[i].push_back(j+N);
G[j+N].push_back(i);
Cap[i][j+N]=1;
}
}
while (BF())
for (vector<int>::iterator it=G[D].begin(); it!=G[D].end(); ++it)
if (V[*it]==1 && Flow[*it][D]<Cap[*it][D])
{
T[D]=*it;
int FMIN=0x3f3f3f3f;
for (i=D; i!=S; i=T[i])
FMIN=min(FMIN, Cap[T[i]][i]-Flow[T[i]][i]);
for (i=D; i!=S; i=T[i])
{
Flow[T[i]][i]+=FMIN;
Flow[i][T[i]]-=FMIN;
}
}
for (i=1; i<=N; i++)
for (j=1; j<=N; j++)
if (Flow[i][j+N]==1)
ANS.push_back(make_pair(i, j));
g << ANS.size() << '\n';
for (i=0; i<ANS.size(); i++)
g << ANS[i].first << ' ' << ANS[i].second << '\n';
f.close();
g.close();
return 0;
}