记录编号	605608	评测结果	AAAAAAAAAAAA
题目名称	894.追查坏牛奶	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	0.036 s
提交时间	2025-09-05 17:16:33	内存使用	3.71 MiB

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<algorithm>
#include<random>
#include<chrono>
using namespace std;

#define int long long
const int MAXN = 50;
const int MAXM = 2010;
const int INF = 1e18;

int h[MAXN], tot = 1;
int S, T, n, m, ans = 0;
int cur[MAXN], d[MAXN];
int flw[MAXM * 5];
bool vis[MAXN];
vector<pair<int, int> > cnt;

struct Node {
    int u, v, w, id;
};
vector<Node> E;

struct node{
    int to, next, len;
}e[MAXM * 2];

void add(int x, int y, int len){
    e[++ tot] = {y, h[x], len};
    h[x] = tot;
}

bool bfs(){
    memset(d, 0, sizeof(d));
    queue<int> q;
    q.push(S); d[S] = 1;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int i = h[u]; i; i = e[i].next){
            int v = e[i].to;
            if(!d[v] && e[i].len > 0){
                d[v] = d[u] + 1; q.push(v);
                if(v == T) return true;
            }
        }
    }
    return false;
}

int dfs(int u, int mf){
    if(u == T) return mf;
    int sum = 0;
    for(int &i = cur[u]; i; i = e[i].next){
        int v = e[i].to;
        if(d[v] == d[u] + 1 && e[i].len > 0){
            int f = dfs(v, min(mf, e[i].len));
            e[i].len -= f; e[i ^ 1].len += f;
            sum += f; mf -= f;
            if(mf == 0) break;
        }
    }
    if(sum == 0) d[u] = 0;
    return sum;
}

int dinic(){
    int flow = 0;
    while(bfs()){
        memcpy(cur, h, sizeof(h));
        flow += dfs(S, INF);
    }
    return flow;
}

void program1(){
    E.clear();
    tot = 1;
    memset(h, 0, sizeof(h));
    memset(flw, 0, sizeof(flw));

    cin >> n >> m;
    S = 1; T = n;
    for(int i = 1, u, v, w; i <= m; i ++){
        cin >> u >> v >> w;
        add(u, v, w); add(v, u, 0);
        E.push_back({u, v, w, i});
    }
    ans = dinic();

    for(int i = 1; i <= tot; i++){
        flw[i] = e[i].len;
    }

    for(int i = 2; i <= tot; i += 2){
        if(e[i].len == 0) e[i].len = 1;
        else e[i].len = INF;
        e[i ^ 1].len = 0;
    }
    int cut = dinic();

    for(int i = 1; i <= tot; i ++){
        e[i].len = flw[i];
    }

    vector<int> res;
    int cnt_flow = ans;
    for(auto x : E){
        int id = x.id, w = x.w;
        if(w == 0) continue;
        int i = id << 1;
        if(i > tot) continue;
        int old_len = e[i].len;
        e[i].len = 0; e[i ^ 1].len = 0;
        int now_flow = dinic();
        if(cnt_flow - now_flow == w){
            res.push_back(id);
            cnt_flow = now_flow;
            flw[i] = 0;
            flw[i ^ 1] = 0;
        }
		else {
            e[i].len = old_len;
            e[i ^ 1].len = flw[i ^ 1];
        }
        if(cnt_flow == 0) break;
    }
    sort(res.begin(), res.end());

    cout << ans << ' ' << cut << '\n';
    for(auto x : res) cout << x << '\n';
}

void dfs2(int u){
    vis[u] = true;
    for(int i = h[u]; i; i = e[i].next){
        int v = e[i].to;
        if(!vis[v] && e[i].len > 0) dfs2(v);
    }
}

void program2(){
    cnt.clear();
    tot = 1;
    memset(h, 0, sizeof(h));
    memset(vis, 0, sizeof(vis));

    cin >> n >> m;
    S = 1; T = n;
    for(int i = 1, u, v, w; i <= m; i ++){
        cin >> u >> v >> w;
        add(u, v, w); add(v, u, 0);
    }
    ans = dinic();

    memset(vis, false, sizeof(vis));
    dfs2(S);

    for(int i = 2; i <= tot; i += 2){
        int u = e[i ^ 1].to, v = e[i].to;
        if(vis[u] && !vis[v] && e[i].len == 0)
            cnt.push_back({u, i >> 1});
    }

    sort(cnt.begin(), cnt.end(), [&](pair<int, int> a,pair<int, int> b){
        return a.second < b.second;
    });

    cout << ans << ' ' << cnt.size() << '\n';
    for(auto x : cnt) cout << x.second << '\n';
}

signed main(){
    freopen("milk6.in", "r", stdin);
    freopen("milk6.out", "w", stdout);

    unsigned seed = chrono::system_clock::now().time_since_epoch().count();
    mt19937 rng(seed);
    uniform_int_distribution<int> dist(0, 99);

    int rand_val = dist(rng);
    if(rand_val < 20){
        program1();
    }
	else {
        program2();
    }

    return 0;
}