Pagini recente » Cod sursa (job #2583144) | Cod sursa (job #1668931) | Cod sursa (job #543760) | Istoria paginii runda/daupentrumata | Cod sursa (job #1870675)
#include <bits/stdc++.h>
using namespace std;
int m,n,x[10010],y[10010],c[1010][1010],i,cst,t[1010],nr,f[1010][1010];
bool ap[5][1010],ok;
vector<int>v[1010],ter,ans;
queue<int>q;
void del()
{
vector<int>aa;
aa.swap(ter);
}
bool bsf()
{
q.push(1);
t[1]=-1;
ok=false;
while(!q.empty())
{
int nod=q.front();
q.pop();
for(auto &it: v[nod])
{
if (t[it] || c[nod][it] == f[nod][it]) continue;
if(it==n)
{
ter.push_back(nod);
ok=true;
continue;
}
t[it]=nod;
q.push(it);
}
}
return ok;
}
void dsf(int nod,int mrk)
{
ap[mrk][nod]=true;
for(auto &it:v[nod])
if(!ap[mrk][it]&&((!mrk&&c[nod][it]>f[nod][it])||(mrk&&c[it][nod]>f[it][nod])))dsf(it,mrk);
}
int main()
{
freopen("critice.in","r",stdin);
freopen("critice.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1; i<=m; ++i)
{
scanf("%d%d%d",&x[i],&y[i],&cst);
v[x[i]].push_back(y[i]);
v[y[i]].push_back(x[i]);
c[x[i]][y[i]]=cst;
c[y[i]][x[i]]=cst;
}
while(bsf())
{
for(auto &it: ter)
{
t[n]=it;
int nod=n;
int mi=INT_MAX;
while(t[nod]!=-1)
{
mi=min(mi,c[t[nod]][nod]-f[t[nod]][nod]);
nod=t[nod];
}
nod=n;
while(t[nod]!=-1)
{
f[nod][t[nod]]-=mi;
f[t[nod]][nod]+=mi;
nod=t[nod];
}
}
del();
for(i=1; i<=n; ++i)
t[i]=0;
}
dsf(1,0);
dsf(n,1);
for(i=1; i<=m; ++i)
if((f[x[i]][y[i]]==c[x[i]][y[i]]||f[y[i]][x[i]]==c[y[i]][x[i]])&&((ap[0][x[i]]&&ap[1][y[i]])||(ap[1][x[i]]&&ap[0][y[i]])))++nr,ans.push_back(i);
printf("%d\n",nr);
for(auto &it:ans)
{
printf("%d\n",it);
}
return 0;
}