记录编号	366894	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]颓废元	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.065 s
提交时间	2017-01-26 14:28:56	内存使用	7.65 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+10;
struct edge{int f,t,g,o;}w[N];
int n,m,T,a[N],b[N],c[N],head[N],next[N],tail[N],cnt;
void add(int f,int t,int g){
	++cnt;w[cnt]=(edge){f,t,g,cnt+1};
	if (!head[f]) head[f]=tail[f]=cnt;
		else tail[f]=next[tail[f]]=cnt;
	++cnt;w[cnt]=(edge){t,f,0,cnt-1};
	if (!head[t]) head[t]=tail[t]=cnt;
		else tail[t]=next[tail[t]]=cnt;
}
void init(){
	for (int i=1;i<=n;i++) head[i]=0;
	while (cnt) next[cnt--]=0;
	for (int i=1;i<=m;i++) add(a[i],b[i],c[i]);
}
struct st{int x,i,df;}z[N];
int s,t,l[N],top,ans,Min_Cut;
#define V z[top].x
#define E z[top].i
#define F z[top].df
void change(){
	int df=F;ans+=df;
	for (int i=top-1;i;i--){
		w[z[i].i].g-=df;
		w[w[z[i].i].o].g+=df;
		z[i].df-=df;
		if (!z[i].df) top=i;
	}
}
queue<int> Q;
void bfs(){
	for (int i=1;i<=n;i++) l[i]=0;
	l[1]=1;Q.push(1);
	while (!Q.empty()){
		int v=Q.front();Q.pop();
		if (l[n]) continue;
		for (int i=head[v];i;i=next[i])
		if (w[i].g&&!l[w[i].t])
			l[w[i].t]=l[v]+1,Q.push(w[i].t);
	}
}
bool dinic(){
	bfs();
	if (!l[n]) return 0;
	z[top=1]=(st){1,head[1],(int)1e9};
	while (top){
		if (V==n){change();top--;E=next[E];}else
		if (!E){l[V]=0;top--;E=next[E];}else
		if (w[E].g&&l[w[E].t]==l[V]+1)
			z[top+1]=(st){w[E].t,head[w[E].t],min(F,w[E].g)},top++;
		else E=next[E];
	}
	return 1;
}
int dfn[N],low[N],vis[N],fa[N],stack[N],h;
bool ins[N];
void tarjan(int x){
	static int cnt=0;
	low[x]=dfn[x]=++cnt;
	stack[++h]=x;
	ins[x]=1;
	for (int i=head[x];i;i=next[i])
	if (w[i].g){
		int v=w[i].t;
		if (!dfn[v]) tarjan(v),low[x]=min(low[x],low[v]);else
		if (ins[v]) low[x]=min(low[x],dfn[v]);
	}
	if (low[x]==dfn[x]){
		for (int i=h;stack[i]!=x;i--,h--)
			fa[stack[i]]=x,ins[stack[i]]=0;
		fa[x]=x;ins[x]=0;h--;
	}
}
int main()
{
	freopen("JJandLazy.in","r",stdin);
	freopen("JJandLazy.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
	init();while (dinic());Min_Cut=ans;
	for (int i=1;i<=n;i++)
		if (!dfn[i]) tarjan(i);	
	scanf("%d",&T);
	for (int i=1;i<=T;i++){
		int tp,x;
		scanf("%d%d",&tp,&x);
		if (tp==1) puts(!w[x*2-1].g&&fa[a[x]]!=fa[b[x]]?"1":"0");
			else puts(!w[x*2-1].g&&fa[a[x]]==fa[1]&&fa[b[x]]==fa[n]?"1":"0");
	}
	printf("%d\n",Min_Cut);
	int sum=0;
	for (int i=1;i<=m;i++)
	if (!w[i*2-1].g&&fa[a[i]]!=fa[b[i]]){
		int last=c[i];ans=sum+c[i];c[i]=0;
		init();while (dinic());
		if (ans==Min_Cut) printf("%d ",i),sum+=last;
			else c[i]=last;
	}
	puts("");
	return 0;
}