Pagini recente » Cod sursa (job #2952805) | Cod sursa (job #818554) | Cod sursa (job #2885606) | Cod sursa (job #1470328) | Cod sursa (job #2238854)
#include<cstring>
#include<fstream>
#include<iostream>
#include<queue>
#include<vector>
#include<stdlib.h>
#define NMAX (1<<10)
#define oo (1<<30)
using namespace std;
ifstream in("critice.in");
ofstream out("critice.out");
int n,m,x,y,z,minim,no;
int p[NMAX][NMAX],fl[NMAX][NMAX],daddy[NMAX];
bool viz[NMAX];
vector<int>graph[NMAX];
queue<int>chiu;
pair<int,int>edge[10*NMAX];
void scan()
{
in>>n>>m;
for(int i=0;i<m;i++)
{
in>>x>>y>>z;
graph[x].push_back(y);
graph[y].push_back(x);
p[x][y]=p[y][x]=z;
edge[i]=make_pair(x,y);
}
}
bool bf()
{
memset(viz, 0, sizeof(viz));
while(!chiu.empty())
chiu.pop();
chiu.push(1);
viz[1]=1;
while(!chiu.empty())
{
int node=chiu.front();
chiu.pop();
for(size_t i=0;i<graph[node].size();i++)
{
int neigh=graph[node][i];
if(!viz[neigh]&p[node][neigh]>fl[node][neigh])
{
chiu.push(neigh);
daddy[neigh]=node;
viz[neigh]=1;
if(neigh==n)
return true;
}
}
}
return false;
}
void EK()
{
scan();
while(bf())
{
for(int i=0;i<graph[n].size();i++)
{
int vertex=graph[n][i];
if(viz[vertex]&(p[vertex][n]!=fl[vertex][n]))
{
daddy[n]=vertex;
minim=oo;
for(no=n;no!=1;no=daddy[no])
minim= min(minim,p[daddy[no]][no]-fl[daddy[no]][no]);
if(minim!=0)
{
for(no=n;no!=1;no=daddy[no])
{
fl[daddy[no]][no]+=minim;
fl[no][daddy[no]]-=minim;
}
}
}
}
}
}
int visited[NMAX];
void df(int start, int value)
{
visited[start]=value;//value ia valoarea 1 pentru sensul 1->n, iar 2 pentru sensul n->1
for(int i=0;i<graph[start].size();i++)
{
int next=graph[start][i];
if(!visited[next])
if(abs(p[start][next])>abs(fl[start][next]))
df(next,value);
}
}
vector<int>sol;
int main()
{
EK();
df(1,1);
df(n,2);
int i,nosol=0;
for(i=0;i<m;i++)
{
if(visited[edge[i].first]&&visited[edge[i].second]&&visited[edge[i].first]!=visited[edge[i].second])
{
sol.push_back(i+1);
nosol++;
}
}
out<<nosol<<endl;
for(i=0;i<nosol;i++)
out<<sol[i]<<endl;
}