记录编号	605640	评测结果	AAAAAAAAAAAA
题目名称	894.追查坏牛奶	最终得分	100
用户昵称	左清源	是否通过	通过
代码语言	C++	运行时间	0.035 s
提交时间	2025-09-05 19:50:53	内存使用	3.88 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll V=2e9+1,inf=1e18,B=500501;
const int N=40,M=5e3+10;
int n,m,S,T,ver[N],to[M],nxt[M],idx=1;
int now[N],d[N],mk[N],vis[N];
ll val[M];
vector<int>ans;
queue<int>q;
ll maxflow;
void add(int x,int y,ll z){
	to[++idx]=y,nxt[idx]=ver[x],ver[x]=idx,val[idx]=z;
	to[++idx]=x,nxt[idx]=ver[y],ver[y]=idx,val[idx]=0;
}
bool bfs(){
	while(q.size())q.pop();
	for(int i=1;i<=n;i++)now[i]=ver[i],d[i]=0;
	q.push(S),d[S]=1;
	while(q.size()){
		int x=q.front();q.pop();
		for(int i=ver[x];i;i=nxt[i]){
			if(!val[i])continue;
			int y=to[i];
			if(!d[y]){
				d[y]=d[x]+1;
				q.push(y);
				if(y==T)return 1;
			}
		}
	}
	return 0;
}
ll dinic(int x,ll flow){
	if(x==T||!flow)return flow;
	ll used=0,f;int y;
	for(int i=now[x];i;i=nxt[i]){
		now[x]=i,y=to[i];
		if(d[y]==d[x]+1&&val[i]){
			f=dinic(y,min(val[i],flow-used));
			if(!f)d[y]=0;
			else val[i]-=f,val[i^1]+=f,used+=f;
			if(used==flow)break;
		}
	}	
	return used;
}
void flow(){
	ll incf=0;
	while(bfs())while(incf=dinic(S,inf))maxflow+=incf;
	return;
}
void dfs(int x){
	vis[x]=1;
	for(int i=ver[x];i;i=nxt[i]){
        int y=to[i];
        if(!vis[y]&&val[i])dfs(y);
    }
    return;
}
int main(){
	freopen("milk6.in","r",stdin); 
	freopen("milk6.out","w",stdout);
	scanf("%d %d",&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;
	flow();maxflow/=B;
	printf("%lld %lld\n",maxflow%V,maxflow/V);
	dfs(S);
    for(int i=2;i<=idx;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 p:ans)printf("%d\n",p);
	return 0;
}