Pagini recente » Cod sursa (job #898083) | Cod sursa (job #2076742) | Cod sursa (job #2424549) | Cod sursa (job #2958546) | Cod sursa (job #444899)
Cod sursa(job #444899)
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
const int NMAX = 1011;
const int MMAX = 10011;
const int INF = 1000000010;
using namespace std;
int N, M;
int c[NMAX][NMAX];
int f[NMAX][NMAX];
vector<int> G[NMAX];
bool viz[NMAX];
pair<int, int> much[MMAX];
int tata[NMAX];
bool viz1[NMAX];
bool viz2[NMAX];
int rez[NMAX];
void citire()
{
cin >> N >> M;
int x, y, cap;
for(int i = 1 ; i <= M ; i++)
{
cin >> x >> y >> cap;
G[x].push_back(y);
G[y].push_back(x);
c[x][y] = cap;
c[y][x] = cap;
much[i] = (make_pair(x, y));
}
}
inline bool BFS()
{
fill(viz, viz + N + 1, 0);
queue<int> Q;
Q.push(1);
viz[1] = true;
int x;
vector<int> :: iterator it;
while(!Q.empty())
{
x = Q.front();
Q.pop();
if(x != N)
for(it = G[x].begin() ; it != G[x].end() ; it++)
if(!viz[*it] && c[x][*it] > f[x][*it])
{
tata[*it] = x;
viz[*it] = true;
Q.push(*it);
}
}
return viz[N];
}
void FLUX()
{
vector<int> :: iterator it;
while(BFS())
for(it = G[N].begin() ; it != G[N].end() ; it++)
if(viz[*it] && c[N][*it] > f[N][*it])
{
int minim = INF;
tata[N] = *it;
for(int i = N ; i != 1; i = tata[i])
minim = min(minim, c[tata[i]][i] - f[tata[i]][i]);
if(minim)
for(int i = N ; i != 1 ; i = tata[i])
{
f[tata[i]][i] += minim;
f[i][tata[i]] -= minim;
}
}
}
void dfs1(int nod)
{
vector<int> :: iterator it;
viz1[nod] = 1;
for(it = G[nod].begin() ; it != G[nod].end() ; ++it)
if(!viz1[*it] && c[*it][nod] > f[*it][nod] && c[nod][*it] > f[nod][*it])
dfs1(*it);
}
void dfsn(int nod)
{
vector<int> :: iterator it;
viz2[nod] = true;
for(it = G[nod].begin() ; it != G[nod].end() ; ++it)
if(!viz2[*it] && c[*it][nod] > f[*it][nod] && c[nod][*it] > f[nod][*it])
dfsn(*it);
}
void trece()
{
for(int i = 1 ; i <= M ; i++)
if(viz1[much[i].first] && viz2[much[i].second] && c[much[i].first][much[i].second] == f[much[i].first][much[i].second])
rez[++rez[0]] = i;
else if(viz2[much[i].first] && viz1[much[i].second] && c[much[i].second][much[i].first] == f[much[i].second][much[i].first])
rez[++rez[0]] = i;
}
void scrie()
{
printf("%d\n",rez[0]);
for(int i = 1; i <= rez[0] ; i++)
printf("%d\n",rez[i]);
}
int main()
{
freopen("critice.in","r",stdin);
freopen("critice.out","w",stdout);
citire();
FLUX();
dfs1(1);
dfsn(N);
/*for(int i = 1 ; i <= N ; i++)
{
printf("%d ", i);
if(viz1[i])
printf("1 ");
else
printf("0 ");
if(viz2[i])
printf("1\n");
else
printf("0\n");
}*/
trece();
scrie();
return 0;
}