记录编号	236429	评测结果	AAAA
题目名称	[ZOJ 2676]网络战争	最终得分	100
用户昵称	dydxh	是否通过	通过
代码语言	C++	运行时间	0.235 s
提交时间	2016-03-14 08:55:31	内存使用	3.17 MiB

/*
Problem:transformers;
Language:c++;
by dydxh;
2016.03.13;
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<cmath>
#include<set>
#include<utility>
#include<vector>
#include<cstdlib>
#define ll long long
#define ull unsigned long long
using namespace std;
const int oo=2000000000;
const int maxn=105;
const int maxm=405;
const double eps=1e-8;
int n,m,Cnt;
int Fro[maxm],Tor[maxm],Value[maxm],Linkk[maxn];
struct edge{
	int y,next,Th;
	double v;
}e[maxm<<1];
inline int read(){
    int x=0;char ch=getchar();bool flag=false;
    while(ch>'9' || ch<'0') {if(ch=='-') flag=true;ch=getchar();}
    while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return flag?-x:x;
}
inline double myabs(double a){return a<0?-a:a;}
void Insert(int a,int b,double c,int d){
	e[++Cnt].next=Linkk[a],Linkk[a]=Cnt,e[Cnt].y=b,e[Cnt].v=c,e[Cnt].Th=d;
	e[++Cnt].next=Linkk[b],Linkk[b]=Cnt,e[Cnt].y=a,e[Cnt].v=c,e[Cnt].Th=d;
}
double Initial_Sum;
void Initialize(){
	Cnt=1,Initial_Sum=0.0;
	memset(Linkk,0,sizeof(Linkk));
	memset(e,0,sizeof(e));
}
int Ans[maxn];
void ReBuild(double Delta){
	Initialize();Ans[0]=0;
	for(int i=1;i<=m;i++){
		if(Value[i]>Delta) Insert(Fro[i],Tor[i],Value[i]-Delta,i);
		else{
			Initial_Sum+=Delta-Value[i];
			Ans[++Ans[0]]=i;
		}
	}
}
int Head,Tail;
int Q[maxn],Level[maxn];
bool Make_Level(){
	memset(Level,-1,sizeof(Level));
	Q[Tail=1]=1,Level[1]=Head=0;
	while(Head<Tail){
		int Tn=Q[++Head];
		for(int i=Linkk[Tn];i;i=e[i].next){
			int Tmp=e[i].y;
			if(Level[Tmp]!=-1 || e[i].v<eps) continue;
			Level[Tmp]=Level[Tn]+1,Q[++Tail]=Tmp;
		}
	}
	return Level[n]!=-1;
}
double Dfs(int x,double Flow){
	if(x==n) return Flow;
	double D=0,Maxx=0;
	for(int i=Linkk[x];i && Maxx<Flow;i=e[i].next){
		int Tn=e[i].y;
		if(Level[Tn]!=Level[x]+1 || e[i].v<eps) continue;
		D=Dfs(Tn,min(Flow-Maxx,e[i].v));
		if(D<eps) continue;
		e[i].v-=D,e[i^1].v+=D,Maxx+=D;
	}
	if(Maxx<eps) Level[x]=-1;
	return Maxx;
}
double Dinic(){
	double Flower=0.0;
	while(Make_Level())
		Flower+=Dfs(1,oo);
	return Flower;
}
int Col[maxn];
void Dfs(int x){
	Col[x]=1;
	for(int i=Linkk[x];i;i=e[i].next){
		int Tn=e[i].y;
		if(Col[Tn]!=-1 || e[i].v<eps) continue;
		Dfs(Tn);
	}
}
void Printer(){
	memset(Col,-1,sizeof(Col));
	Dfs(1);
	for(int i=1;i<=n;i++){
		for(int j=Linkk[i];j;j=e[j].next){
			int Tn=e[j].y;
			if(Col[i]==1 && Col[Tn]==-1 && e[j].v<eps){
				Ans[++Ans[0]]=e[j].Th;
			}
		}
	}
	sort(Ans+1,Ans+1+Ans[0]);
	printf("%d\n",Ans[0]);
	for(int i=1;i<=Ans[0];i++) printf("%d ",Ans[i]);
	printf("\n");
}
int main(){
    freopen("networkwar.in","r",stdin);
    freopen("networkwar.out","w",stdout);
	n=read(),m=read();
	while(n || m){
		double Leftt=-1.0,Rightt=0.0;
		for(int i=1;i<=m;i++){
			Fro[i]=read(),Tor[i]=read(),Value[i]=read();
			if(Value[i]>Rightt) Rightt=Value[i];
			if(Value[i]<Leftt || Leftt==-1.0) Leftt=Value[i];
		}
		Leftt-=0.05,Rightt+=0.05;
		while(Leftt+eps<Rightt){
			double Mid=(Leftt+Rightt)/2;
			ReBuild(Mid);
			Initial_Sum-=Dinic();
			if(myabs(Initial_Sum)<eps) break;
			else if(Initial_Sum>0) Rightt=Mid;
			else Leftt=Mid;
		}
		Printer();
		n=read(),m=read();
		if(n || m) printf("\n");
	}
    return 0;
}