Pagini recente » Diferente pentru home intre reviziile 902 si 157 | Cod sursa (job #1235743) | Monitorul de evaluare | Cod sursa (job #1523742) | Cod sursa (job #996932)
Cod sursa(job #996932)
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#define NM 1010
using namespace std;
ifstream f("critice.in");
ofstream g("critice.out");
int N, M;
int Cap[NM][NM], Flow[NM][NM];
int A[10*NM], B[10*NM];
vector<int> G[NM];
vector<int> ANS;
queue<int> Q;
int T[NM];
bool PathS[NM], PathD[NM];
bool BF ()
{
memset(PathS, 0, sizeof(PathS));
PathS[1]=1;
Q.push(1);
int node;
vector<int>::iterator it;
while (!Q.empty())
{
node=Q.front();
Q.pop();
if (node==N) continue;
for (it=G[node].begin(); it!=G[node].end(); ++it)
if (PathS[*it]==0 && Cap[node][*it]>Flow[node][*it])
{
T[*it]=node;
PathS[*it]=1;
Q.push(*it);
}
}
return PathS[N];
}
void DF (int node, bool Path[])
{
Path[node]=1;
for (vector<int>::iterator it=G[node].begin(); it!=G[node].end(); ++it)
if (Path[*it]==0 && Cap[node][*it]>Flow[node][*it] && Cap[*it][node]>Flow[*it][node])
DF(*it, Path);
}
int main ()
{
f >> N >> M;
for (int i=1; i<=M; i++)
{
int a, b, c;
f >> a >> b >> c;
Cap[a][b]=Cap[b][a]=c;
G[a].push_back(b);
G[b].push_back(a);
A[i]=a;
B[i]=b;
}
while (BF())
for (vector<int>::iterator it=G[N].begin(); it!=G[N].end(); ++it)
if (PathS[*it] && Flow[*it][N]!=Cap[*it][N])
{
T[N]=*it;
int FMIN=0x3f3f3f3f;
for (int i=N; i!=1; i=T[i])
FMIN=min(FMIN, Cap[T[i]][i]-Flow[T[i]][i]);
for (int i=N; i!=1; i=T[i])
{
Flow[T[i]][i]+=FMIN;
Flow[i][T[i]]-=FMIN;
}
}
memset(PathS, 0, sizeof(PathS));
memset(PathD, 0, sizeof(PathD));
DF(1, PathS);
DF(N, PathD);
for (int i=1; i<=M; i++)
if ((PathS[A[i]]==1 && PathD[B[i]]==1) || (PathS[B[i]]==1 && PathD[A[i]]==1))
ANS.push_back(i);
g << ANS.size() << '\n';
for (int i=0; i<ANS.size(); i++)
g << ANS[i] << '\n';
f.close();
g.close();
return 0;
}