记录编号	605611	评测结果	AAAAAAAAWWAA
题目名称	894.追查坏牛奶	最终得分	83
用户昵称	李奇文	是否通过	未通过
代码语言	C++	运行时间	0.186 s
提交时间	2025-09-05 17:17:56	内存使用	3.78 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=100,inf=0x3f3f3f3f,M=3005;
int n,m;
int a[N][N],v[M],p[M];
struct node{
	int x,y,z,id;
}f[M];
bool cmp(node hs,node sh){
	return hs.z>sh.z;
}
int EK(){
	int ans=0;
	while(1){
		memset(v,0,sizeof(v));
		memset(p,0,sizeof(p));
		v[1]=inf;
		queue<int>q;
		q.push(1);
		while(!q.empty()){
			int f=q.front();
			q.pop();
			for(int i=1;i<=n;i++){
				if(a[f][i]&&v[i]==0){
					q.push(i);
					p[i]=f;
					v[i]=min(v[f],a[f][i]);
				}
			}
		}
		if(v[n]==0){
			break;
		}
		ans+=v[n];
		int tp=n;
		while(p[tp]!=0){
			a[p[tp]][tp]-=v[n];
			a[tp][p[tp]]+=v[n];
			tp=p[tp];
		}
	}
	return ans;
}
int ccsl[M],cnt;
int main(){
	freopen("milk6.in","r",stdin);
	freopen("milk6.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>f[i].x>>f[i].y>>f[i].z;
		f[i].id=i;
	}
	for(int i=1;i<=m;i++){
		a[f[i].x][f[i].y]+=f[i].z;
	}
	sort(f+1,f+1+m,cmp);
	int ans=EK(),sum=0;
	memset(a,0,sizeof(a));
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			if(j==i) continue;
			a[f[j].x][f[j].y]+=f[j].z;
		}
		int res=EK();
		if(ans-res==f[i].z){
			ccsl[++cnt]=f[i].id;
			sum++;
		}
	}
	cout<<ans<<" "<<sum<<"\n";
	sort(ccsl+1,ccsl+1+cnt);
	for(int i=1;i<=cnt;i++){
		cout<<ccsl[i]<<"\n";
	}
	return 0;
}