题意：求所有最小割中的最小边数。
tags： 真是骚操作。。
对所有边都乘上一个很大的数 MX，再加上 1，然后只要求出最小割对 MX 取一下模即是答案。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 1005; int n; int tot, dis[N], head[N], cur[N], remain[N<<1]; struct Edge{ int to, next; } e[N<<1]; void Addedge(int u,int v,int w) { e[tot]={v,head[u]}; remain[tot]=w; head[u]=tot++; e[tot]={u,head[v]}; remain[tot]=0; head[v]=tot++; } queue<int > q; bool bfs(int st, int ed) { for(int i=0; i<N; ++i) cur[i]=head[i]; mes(dis, -1); while(!q.empty()) q.pop(); q.push(st); dis[st]=0; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u]; i!=-1; i=e[i].next) { int to=e[i].to; if(dis[to]==-1 && remain[i]) { q.push(to); dis[to]=dis[u]+1; if(to==ed) return true; } } } return false; } int dfs(int now, int ed, int flow) { if(now==ed || flow==0) return flow; int s, ans=0; for(int &i=cur[now]; i!=-1; i=e[i].next) { int to=e[i].to; if(dis[to]==dis[now]+1 && (s=dfs(to,ed,min(flow,remain[i]))) ) { ans+=s, flow-=s; remain[i]-=s, remain[i^1]+=s; if(flow==0) break; } } return ans; } int dinic(int st, int ed) { int s, ans=0; while(bfs(st,ed)) while(s=dfs(st,ed,INF)) ans+=s; return ans; } void Init() { mes(head, -1); tot=0; } int m, st, ed, u, v, w; int main() { int T; scanf("%d", &T); while(T--) { Init(); scanf("%d%d%d%d", &n, &m, &st, &ed); rep(i,1,m) { scanf("%d%d%d", &u, &v, &w); Addedge(u, v, w*N+1); } printf("%d ", (dinic(st, ed)%N)); } return 0; }