记录编号	189920	评测结果	AAAA
题目名称	[ZOJ 2676]网络战争	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.250 s
提交时间	2015-09-30 16:35:04	内存使用	0.37 MiB

#include<cstdio>
#include<iostream>
#include<deque>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int SIZEN=110,INF=0x7fffffff,SIZEM=1610;
const double eps=1e-5;
int n,m,tot=0;
deque<int> s[SIZEN],Q;
int ma=0;
double L[SIZEN];
bool T[SIZEN];//是否与1连通
int H[SIZEN];
bool use[SIZEM];
class poi
{
public:
	int fr[SIZEM],to[SIZEM],c[SIZEM],t;
	poi()
	{
		memset(fr,0,sizeof(fr));memset(to,0,sizeof(to));memset(c,0,sizeof(c));t=0;
	}
	void add(int a,int b,int d)
	{
		t++;
		fr[t]=a,to[t]=b,c[t]=d;
	}
}G;
class miku
{
public:
	int fr,to,id;
	double c;
	miku(){}
	miku(int a,int b,double d,int e)
	{
		fr=a,to=b,c=d,id=e;
	}
};
miku E[SIZEM];
bool read()
{
	if(scanf("%d%d",&n,&m)==EOF) return 0;
	if(n==0||m==0) return 0;
	int fr,to,c;
	ma=0;
	G.t=0;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&fr,&to,&c);
		if(c>ma) ma=c;
		G.add(fr,to,c);
	}
	return 1;
}
void add(int fr,int to,double c,int id)
{
	s[fr].push_back(tot);
	E[tot++]=miku(fr,to,c,id);
}
double graph(double a)
{
	double ans=0.0;
	memset(use,0,sizeof(use));
	for(int i=1;i<=G.t;i++)
	{
		if(G.c[i]-a<eps)
		{
			use[i]=1,ans+=G.c[i]-a;
			//cout<<a<<" "<<i<<" "<<ans<<endl;
		}
		else
		{
			add(G.fr[i],G.to[i],G.c[i]-a,i);add(G.to[i],G.fr[i],0,i);
			add(G.to[i],G.fr[i],G.c[i]-a,i);add(G.fr[i],G.to[i],0,i);
		}
	}
	return ans;
}
void push(int x,int t)
{
	miku &v=E[t];
	double flow=min(L[x],v.c);
	L[x]-=flow,L[v.to]+=flow,v.c-=flow,E[t^1].c+=flow;
	if(v.to!=1&&v.to!=n&&L[v.to]>eps) Q.push_back(v.to);
}
void use_up(int x)
{
	while(L[x]>eps)
	{
		int mi=INF;
		for(int i=0;i<s[x].size();i++)
		{
			miku &v=E[s[x][i]];
			if(v.c<eps) continue;
			if(H[v.to]==H[x]-1)
			{
				push(x,s[x][i]);
				if(L[x]<eps) return;
			}
			else if(mi>H[v.to]) mi=H[v.to];
		}
		H[x]=mi+1;
	}
}
double maxflow(double a)
{
	double ans=0.0;
	//cout<<a<<" "<<tot<<endl;
	for(int i=1;i<=n;i++) s[i].clear();
	memset(L,0,sizeof(L));memset(H,0,sizeof(H));
	ans+=graph(a);
	H[1]=n;L[1]=INF;
	if(H[1]>5) H[1]=5;
	for(int i=0;i<s[1].size();i++) push(1,s[1][i]);
	while(!Q.empty())
	{
		int x=Q.front();Q.pop_front();
		use_up(x);
	}
	//cout<<ans<<" "<<L[n]<<endl;
	ans+=L[n];
	return ans;
}
void dfs(int x)
{
	T[x]=1;
	for(int i=0;i<s[x].size();i++)
	{
		miku v=E[s[x][i]];
		if(!T[v.to]&&v.c>eps)
		{
			dfs(v.to);
		}
	}
}
void print()
{
	int ans=0;
	memset(T,0,sizeof(T));
	dfs(1);
	for(int i=1;i<=n;i++)
		for(int j=0;j<s[i].size();j++)
		{
			miku v=E[s[i][j]];
			if((!T[i]&&T[v.to])||(T[i]&&!T[v.to]))
				use[v.id]=1;
		}
	for(int i=0;i<=m;i++)
		if(use[i]==1) ans++;
	printf("%d\n",ans);
	for(int i=1;i<=m;i++)
		if(use[i]==1)
			printf("%d ",i);
	printf("\n");
	printf("\n");
}
void work()
{
	double l,r,mid;
	l=0.0;r=ma+0.0;
	for(int i=0;i<=50;i++)
	{
		mid=(r+l)/2;
		tot=0;
		if(maxflow(mid)>eps) l=mid;
		else r=mid;
		if((r-l)<eps) break;
	}
	print();
}
int  main()
{
	freopen("networkwar.in","r",stdin);
	freopen("networkwar.out","w",stdout);
	while(read()) work();
	return 0;
}