#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;const int MAXN = 110;const int MAXE = 3010;const int INF = 0x3fff3fff;struct SAP { int head[MAXN], dis[MAXN], pre[MAXN], cur[MAXN], gap[MAXN]; int to[MAXE], next[MAXE], flow[MAXE]; int n, st, ed, ecnt; void init() { memset(head, 0, sizeof(head)); ecnt = 2; } void add_edge(int u, int v, int c) { to[ecnt] = v; flow[ecnt] = c; next[ecnt] = head[u]; head[u] = ecnt++; to[ecnt] = u; flow[ecnt] = 0; next[ecnt] = head[v]; head[v] = ecnt++; //printf("%d->%d flow = %dn", u, v, c); } void bfs() { memset(dis, 0x3f, sizeof(dis)); queue<int> que; que.push(ed); dis[ed] = 0; while(!que.empty()) { int u = que.front(); que.pop(); ++gap[dis[u]]; for(int p = head[u]; p; p = next[p]) { int &v = to[p]; if(flow[p ^ 1] && dis[v] > n) { dis[v] = dis[u] + 1; que.push(v); } } } } int Max_flow(int ss, int tt, int nn) { st = ss; ed = tt; n = nn; int ans = 0, minFlow = INF, u; for(int i = 0; i <= n; ++i) { cur[i] = head[i]; gap[i] = 0; } u = pre[st] = st; bfs(); while(dis[st] < n) { bool flag = false; for(int &p = cur[u]; p; p = next[p]) { int &v = to[p]; if(flow[p] && dis[u] == dis[v] + 1) { flag = true; minFlow = min(minFlow, flow[p]); pre[v] = u; u = v; if(u == ed) { ans += minFlow; while(u != st) { u = pre[u]; flow[cur[u]] -= minFlow; flow[cur[u] ^ 1] += minFlow; } minFlow = INF; } break; } } if(flag) continue; int minDis = n - 1; for(int p = head[u]; p; p = next[p]) { int &v = to[p]; if(flow[p] && minDis > dis[v]) { minDis = dis[v]; cur[u] = p; } } if(--gap[dis[u]] == 0) break; gap[dis[u] = minDis + 1]++; u = pre[u]; } return ans; } int mark[MAXN]; void make_cut() { memset(mark, 0, sizeof(mark)); queue<int> que; que.push(st); mark[st] = 1; while(!que.empty()) { int u = que.front(); que.pop(); for(int p = head[u]; p; p = next[p]) { int &v = to[p]; if(flow[p] && !mark[v]) { mark[v] = 1; que.push(v); } } } que.push(ed); mark[ed] = 2; while(!que.empty()) { int u = que.front(); que.pop(); for(int p = head[u]; p; p = next[p]) { int &v = to[p]; if(flow[p ^ 1] && !mark[v]) { mark[v] = 2; que.push(v); } } } }} G;int from[MAXE], to[MAXE];int n, m, L, c;int main() { while(scanf("%d%d%d", &n, &m, &L) != EOF) { if(n == 0) break; int ss = n + m + 1, tt = 0; G.init(); for(int i = 1; i <= n; ++i) G.add_edge(ss, i, INF); for(int i = 1; i <= L; ++i) { scanf("%d%d%d", &from[i], &to[i], &c); G.add_edge(from[i], to[i], c); } G.Max_flow(ss, tt, ss); G.make_cut(); bool flag = false; for(int i = 1; i <= L; ++i) { int &u = from[i], &v = to[i]; if(G.mark[u] == 1 && G.mark[v] == 2) { if(flag) printf(" "); printf("%d", i); flag = true; } } puts(""); }}
