记录编号	81344	评测结果	AAAAAAAAAAAA
题目名称	追查坏牛奶	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.048 s
提交时间	2013-11-11 20:12:39	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<deque>
using namespace std;
typedef long long ll;
const ll SIZEN=38;
const ll INF=1e17;
const ll MOD=1001;
class EDGE{
public:
	ll pos;//pos>0表示为图中的边
	ll from,to;
	ll cap,flow;
	bool able;
	EDGE(){
		able=true;
		flow=0;
	}
};
vector<EDGE> edges;
vector<ll> c[SIZEN];
ll e[SIZEN]={0};
ll h[SIZEN]={0};
deque<ll> Q;//overflow
ll S,T;
ll n;
ll mincost;
ll minroute;
void addedge(ll pos,ll from,ll to,ll cap){
	EDGE temp;
	temp.pos=pos;temp.from=from;temp.to=to;temp.cap=cap;
	edges.push_back(temp);c[from].push_back(edges.size()-1);
	temp.pos=0;temp.from=to,temp.to=from,temp.cap=0;
	edges.push_back(temp);c[to].push_back(edges.size()-1);
}
void push(ll x,ll k){
	EDGE& now=edges[k];
	if(!now.able) return;
	ll df;
	df=min(now.cap-now.flow,e[x]);
	if(df<=0) return;
	edges[k].flow+=df;edges[k^1].flow-=df;
	e[x]-=df;e[now.to]+=df;
	if(now.to!=S&&now.to!=T&&e[now.to]) Q.push_back(now.to);
}
void singlenode(ll x){
	ll nowmin;
	ll i;
	EDGE now;
	while(e[x]){
		nowmin=INF;
		for(i=0;i<c[x].size();i++){
			now=edges[c[x][i]];
			if(!now.able) continue;
			if(now.cap<=now.flow) continue;
			if(h[now.to]==h[x]-1){
				push(x,c[x][i]);
				if(!e[x]) return;
			}
			if(now.cap>now.flow) nowmin=min(nowmin,h[now.to]);
		}
		h[x]=nowmin+1;
	}
}
void clear(void){
	ll i;
	for(i=0;i<edges.size();i++) edges[i].flow=0;
	for(i=1;i<=n;i++) h[i]=e[i]=0;
	Q.clear();
}
void init(void){
	h[S]=n;
	e[S]=INF;
	ll i;
	for(i=0;i<c[S].size();i++) push(S,c[S][i]);
}
ll maxflow(void){
	ll x;
	while(!Q.empty()){
		x=Q.front();
		Q.pop_front();
		singlenode(x);
	}
	ll ans=0;
	ll i;
	for(i=0;i<c[S].size();i++){
		if(!edges[c[S][i]].able) continue;
		ans+=edges[c[S][i]].flow;
	}
	return ans;
}
void read(void){
	ll m;
	scanf("%lld%lld",&n,&m);
	S=1,T=n;
	ll i;
	ll from,to,cap;
	for(i=1;i<=m;i++){
		scanf("%lld%lld%lld",&from,&to,&cap);
		addedge(i,from,to,cap*MOD+1);
	}
}
void get_mincut(void){
	ll tot=0;
	ll i=0;
	ll nowans;
	bool flag[1001]={0};
	for(i=0;i<edges.size();i+=2){
		if(edges[i].cap==edges[i].flow) flag[edges[i].pos]=true;
	}
	i=0;
	while(tot<=minroute&&i<edges.size()){
		if(!flag[edges[i].pos]){
			i+=2;
			continue;
		}
		edges[i].able=edges[i+1].able=false;
		clear();
		init();
		nowans=maxflow();
		if(mincost-nowans==edges[i].cap){//最小割中的边
			mincost=nowans;
			printf("%lld ",edges[i].pos);
			tot++;
			if(tot==minroute) return;
		}
		else{
			edges[i].able=edges[i+1].able=true;
		}
		i+=2;
	}
}
void work(void){
	clear();
	init();
	mincost=maxflow();
	minroute=mincost%MOD;
	printf("%lld ",mincost/MOD);
	printf("%lld\n",minroute);
	get_mincut();
}
int main(){
	freopen("milk6.in","r",stdin);
	freopen("milk6.out","w",stdout);
	read();
	work();
	return 0;
}