记录编号	605653	评测结果	AAAAAAAAAAAA
题目名称	894.追查坏牛奶	最终得分	100
用户昵称	Hollow07	是否通过	通过
代码语言	C++	运行时间	0.035 s
提交时间	2025-09-05 21:15:37	内存使用	3.91 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll V=2e9+1,B=500501;
ll n,m,s,t,head[6000],to[6000],nxt[6000],cnt=1;
ll now[6000],dep[6000],vis[6000];
ll val[6000];
vector<ll>ans;
queue<ll>q;
ll ans1;

void add(ll x,ll y,ll z){
	to[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt,val[cnt]=z;
	to[++cnt]=x,nxt[cnt]=head[y],head[y]=cnt,val[cnt]=0;
}

bool bfs(){
	while(q.size())q.pop();
	for(int i=1;i<=n;i++) now[i]=head[i],dep[i]=0;
	q.push(s),dep[s]=1;
	while(q.size()){
		ll x=q.front();q.pop();
		for(int i=head[x];i;i=nxt[i]){
			if(!val[i])continue;
			int y=to[i];
			if(!dep[y]){
				dep[y]=dep[x]+1;
				q.push(y);
				if(y==t)return 1;
			}
		}
	}
	return 0;
}

ll dfs(ll x,ll flow){
	if(x==t||!flow)return flow;
	ll res=0,f,y;
	for(int i=now[x];i;i=nxt[i]){
		now[x]=i,y=to[i];
		if(dep[y]==dep[x]+1&&val[i]){
			f=dfs(y,min(val[i],flow-res));
			if(!f) dep[y]=0;
			else val[i]-=f,val[i^1]+=f,res+=f;
			if(res==flow)break;
		}
	}	
	return res;
}

void dinic(){
	ll res=0;
	while(bfs()){
		while(res=dfs(s,1e18)) ans1+=res;
	}
	return;
}

void dfs2(ll x){
	vis[x]=1;
	for(int i=head[x];i;i=nxt[i]){
        ll y=to[i];
        if(!vis[y]&&val[i]) dfs2(y);
    }
    return;
}

int main(){
//	freopen("in.in","r",stdin);
	freopen("milk6.in","r",stdin); 
	freopen("milk6.out","w",stdout);
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=m;i++){
		ll u,v,w;
		scanf("%lld %lld %lld",&u,&v,&w);
		add(u,v,i+w*B+V*B);
	}
	s=1,t=n;
	dinic();ans1/=B;
	printf("%lld %lld\n",ans1%V,ans1/V);
	dfs2(s);
    for(int i=2;i<=cnt;i+=2){
        int u=to[i^1],v=to[i];
        if(vis[u]&&!vis[v]&&!val[i]) ans.push_back(i>>1);
    }
	sort(ans.begin(),ans.end());
	for(auto i:ans)printf("%d\n",i);
	return 0;
}