记录编号	276468	评测结果	AAAA
题目名称	[ZOJ 2676]网络战争	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.078 s
提交时间	2016-07-03 23:49:35	内存使用	1.65 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>
using namespace std;
const int maxn=10010;
const int maxm=40010;
const double eps=1e-7;
const int INF=10000000;
int n,m,e[maxm][3];
int cnt,fir[maxn],to[maxm],nxt[maxm],ID[maxm];
double cap[maxn];
void addedge(int a,int b,double c,int id){
	nxt[++cnt]=fir[a];
	fir[a]=cnt;
	ID[cnt]=id;
	cap[cnt]=c;
	to[cnt]=b;
}

queue<int>q;
int dis[maxn];
bool BFS(int s,int t){
	memset(dis,0,sizeof(dis));
	dis[t]=1;q.push(t);
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=fir[x];i;i=nxt[i])
			if(!dis[to[i]]){
				dis[to[i]]=dis[x]+1;
				q.push(to[i]);
			}
	}	
	return dis[s];
}

int fron[maxn];
int gap[maxn],path[maxn];
double ISAP(int s,int t){
	if(!BFS(s,t))return 0;
	for(int i=s;i<=t;i++)++gap[dis[i]];
	for(int i=s;i<=t;i++)fron[i]=fir[i];
	int p=s;
	double f,ret=0;
	while(dis[s]<=t){
		if(p==t){
			f=INF;
			while(p!=s){
				f=min(f,cap[path[p]]);
				p=to[path[p]^1];				
			}
			ret+=f;p=t;
			while(p!=s){
				cap[path[p]]-=f;
				cap[path[p]^1]+=f;
				p=to[path[p]^1];
			}
		}
		int &ii=fron[p];
		for(;ii;ii=nxt[ii])
			if(cap[ii]>eps&&dis[p]==dis[to[ii]]+1)
				break;
		if(ii)
			path[p=to[ii]]=ii;
		else{
			if(--gap[dis[p]]==0)break;
			int minn=t+1;
			for(int i=fir[p];i;i=nxt[i])
				if(cap[i]>eps)minn=min(minn,dis[to[i]]);
			++gap[dis[p]=minn+1];ii=fir[p];
			if(p!=s)p=to[path[p]^1];	
		}			
	}
	return ret;
}

int ch[maxm],ans;
void Init(){
	memset(fir,0,sizeof(fir));
	memset(gap,0,sizeof(gap));
	memset(ch,0,sizeof(ch));
	cnt=1;
}


double Solve(double lam){
	Init();
	double ret=0.0;
	for(int i=1;i<=m;i++){
		if(e[i][2]-lam<-eps){
			ret+=e[i][2]-lam;
			ch[i]=1;
		}
		else{
			addedge(e[i][0],e[i][1],e[i][2]-lam,i);
			addedge(e[i][1],e[i][0],e[i][2]-lam,i);
		}
	}
	ret+=ISAP(1,n);
	for(int i=2;i<=cnt;i++)
		if(fabs(cap[i])<eps&&ID[i])ch[ID[i]]=1;
	return ret;	
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("networkwar.in","r",stdin);
	freopen("networkwar.out","w",stdout);
#endif
	while(true){
		scanf("%d%d",&n,&m);
		if(!n&&!m)break;
		for(int i=1;i<=m;i++)
			for(int j=0;j<=2;j++)
				scanf("%d",&e[i][j]);
		double lo=eps,hi=INF,lam;
		for(int t=1;t<=30;t++){
			lam=(lo+hi)/2;
			if(Solve(lam)>eps)
				lo=lam;
			else 
				hi=lam;
			if(hi-lo<eps)break;	
		}
		ans=0;
		for(int i=1;i<=m;i++)
			if(ch[i])ans+=1;
		printf("%d\n",ans);
		for(int i=1;i<=m;i++)
			if(ch[i])printf("%d ",i);
		printf("\n\n");		
	}
	return 0;	
}