记录编号	577631	评测结果	AAAAAAAAAAAA
题目名称	追查坏牛奶	最终得分	100
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	通过
代码语言	C++	运行时间	1.069 s
提交时间	2022-11-15 19:11:49	内存使用	2.17 MiB

/*
* 第一次先跑最大流找到最小割
* 这个时候满流边可能是最小割的一部分
* 因为选一个非满流边不如选所有他后继的满流边
* 然后把非满流边流量赋为INF，满流边赋1
* 在新网络上跑最大流
* 再枚举每一条边删边(只枚举边权为1且满流的)
* 如果删完这条边总流量减少1，那就选走
* 不复原
* 否则复原
*/
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define int long long int
using namespace std;
const int N = 100, M = 40000;
int head[N], val[M], to[M], nxt[M],vals[M],id[M];
int layer[N],cnt=1,n,m,S,T;
void ADD(int x, int y, int v,int idx)
{
	to[++cnt] = y;
	val[cnt] = v;
	nxt[cnt] = head[x];
	head[x] = cnt;
	vals[cnt] = v;
	id[cnt] = idx;
	to[++cnt] = x;
	val[cnt] = 0;
	nxt[cnt] = head[y];
	head[y] = cnt;
	vals[cnt] = 0;
	id[cnt] = idx;
}
bool BFS()
{
	queue<int> q;
	memset(layer, 0, sizeof(layer));
	q.push(S);
	layer[S] = 1;
	while (q.size())
	{
		int now = q.front();
		q.pop();
		for (int i = head[now]; i; i = nxt[i])
		{
			int y = to[i];
			if (layer[y] || !val[i])
				continue;
			layer[y] = layer[now] + 1;
			q.push(y);
		}
	}
	if (layer[T])
		return 1;
	return 0;
}
int Update(int x, int flow)
{
	if (x == T)
	{
		return flow;
	}
	int rest = flow;
	for (int i = head[x]; i; i = nxt[i])
	{
		int y = to[i];
		if (layer[y] != layer[x] + 1 || !val[i])
			continue;
		int k = Update(y, min(rest, val[i]));
		if (!k)
		{
			layer[y] = 0;
			continue;
		}
		rest -= k;
		val[i] -= k;
		val[i ^ 1] += k;
	}
	return flow - rest;
}
int Dinic()
{
	int kel,maxflow=0;
	while (BFS())
	{
		while (kel = Update(S, 0x3f3f3f3f))
		{
			//cout << "S";
			maxflow += kel;
		}
	}
	return maxflow;
}
void Change1()
{
	for (int i = 2; i <= cnt; i += 2)
	{
		if (val[i])
		{
			val[i] = 0x3f3f3f3f;
			val[i ^ 1] = 0;
		}
		else
		{
			val[i] = 1;
			val[i ^ 1] = 0;
		}
	}
}
struct EDGE
{
	int x, y, v,ids;
};
EDGE e[M];
bool Function(EDGE A, EDGE B)
{
	if (A.v == B.v)
		return A.ids < B.ids;
	return A.v > B.v;
}
signed main()
{
	freopen("milk6.in", "r", stdin);
	freopen("milk6.out", "w", stdout);
	scanf("%lld%lld", &n, &m);
	int a1, a2, a3;
	for (int i = 1; i <= m; i++)
	{
		scanf("%lld%lld%lld", &a1, &a2, &a3);
		e[i].x = a1;
		e[i].y = a2;
		e[i].v = a3;
		e[i].ids = i;
		//ADD(a1, a2, a3);
	}
	sort(e + 1, e + 1 + m,Function);
	for (int i = 1; i <= m; i++)
	{
		ADD(e[i].x, e[i].y, e[i].v, e[i].ids);
	}
	S = 1;
	T = n;
	int MINCOST = Dinic();
	Change1();
	int MINLINE = Dinic();
	memcpy(val, vals, sizeof(val));
	int anss[M], tot = 0;
	printf("%lld %lld\n", MINCOST, MINLINE);
	for (int i = 2; i <= cnt; i+=2)
	{
		int STD = val[i];
		val[i] = 0;
		val[i ^ 1] = 0;
		int SDS = Dinic();
		if (SDS== MINCOST - STD)
		{
			anss[++tot] = id[i];
			MINCOST-=STD;
			vals[i] = 0;
			vals[i ^ 1] = 0;
		}
		memcpy(val, vals, sizeof(val));
		if (MINCOST == 0)
			break;
	}
	sort(anss + 1, anss + 1 + tot);
	for (int i = 1; i <= tot; i++)
	{
		printf("%lld\n", anss[i]);
	}
	return 0;
}