P1344 [USACO4.4]追查坏牛奶Pollutant Control 最小割

本文主要是介绍P1344 [USACO4.4]追查坏牛奶Pollutant Control 最小割，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

你第一天接手三鹿牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批有三聚氰胺的牛奶。很不幸，你发现这件事的时候，有三聚氰胺的牛奶已经进入了送货网。这个送货网很大，而且关系复杂。你知道这批牛奶要发给哪个零售商，但是要把这批牛奶送到他手中有许多种途径。送货网由一些仓库和运输卡车组成，每辆卡车都在各自固定的两个仓库之间单向运输牛奶。在追查这些有三聚氰胺的牛奶的时候，有必要保证它不被送到零售商手里，所以必须使某些运输卡车停止运输，但是停止每辆卡车都会有一定的经济损失。你的任务是，在保证坏牛奶不送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。

输入输出格式

输入格式：

第一行: 两个整数N(2<=N<=32)、M(0<=M<=1000), N表示仓库的数目，M表示运输卡车的数量。仓库1代表发货工厂，仓库N代表有三聚氰胺的牛奶要发往的零售商。第2..M+1行: 每行3个整数Si,Ei,Ci。其中Si,Ei表示这辆卡车的出发仓库，目的仓库。Ci(0 <= C i <= 2,000,000) 表示让这辆卡车停止运输的损失。

输出格式：

两个整数C、T：C表示最小的损失，T表示在损失最小的前提下，最少要停止的卡车数。

输入输出样例

输入样例#1：复制

输出样例#1：复制

60 1


很明显是一道求最小割的题目  还要求求最小割的边集数量

可以采用一种取巧的做法

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
//
#define inf 0x3f3f3f3f
const int N=4e3+44;
const int M=4e3+54;struct edge {ll to, next, w;
} e[M << 1];
int head[N], pos = 1;
void add(ll x, ll y, ll z) {e[++pos] = (edge){y, head[x], z};head[x] = pos;e[++pos] = (edge){x, head[y], 0};head[y] = pos;
}
int level[N];
bool bfs(int s, int t) {memset(level, 0, sizeof level);queue<ll> q;level[s] = 1;q.push(s);while (!q.empty()) {int pos = q.front();q.pop();for (int i = head[pos]; i; i = e[i].next) {int nx = e[i].to;if (!e[i].w || level[nx]) continue;level[nx] = level[pos] + 1;q.push(nx);}}return level[t];
}
ll dfs(ll s, ll t, ll flow) {if (s == t) return flow;ll ret = 0;for (int i = head[s]; flow && i; i = e[i].next) {int nx = e[i].to;if (level[nx] == level[s] + 1 && e[i].w) {ll tmp = dfs(nx, t, min(flow, e[i].w));e[i].w -= tmp;e[i ^ 1].w += tmp;flow -= tmp;ret += tmp;}}if (!ret) level[s] = 0;return ret;
}
ll dinic(ll s, ll t) {ll ret = 0;while (bfs(s, t)) ret += dfs(s, t, inf);return ret;
}
ll n,m,s,t,T,a,b,c,x,k,c2,sum;int main()
{cin>>n>>m;rep(i,1,m){scanf("%lld%lld%lld",&a,&b,&c);add(a,b,c*(m+1)+1);}ll ans=dinic(1,n);printf("%lld %lld",ans/(m+1),ans%(m+1));return 0;
}