题意：n个点m条边的加权网络，求最少边数的按编号字典序最小的最小割。（n<=32, m<=1000）

#include 
     
      using namespace std;typedef long long ll;struct Gr {	static const int N=33, M=1005, oo=~0u>>1;	struct E { int next, from, to, cap; }e[M<<1];	int ihead[N], cnt, d[N], p[N], gap[N], cur[N];	Gr() { memset(ihead, 0, sizeof ihead); cnt=1; }	Gr & operator=(const Gr &g) {		memcpy(ihead, g.ihead, sizeof g.ihead);		memcpy(e, g.e, sizeof g.e);		cnt=g.cnt;		return *this;	}	void add(int u, int v, int cap) {		e[++cnt]=(E){ihead[u], u, v, cap}; ihead[u]=cnt;		e[++cnt]=(E){ihead[v], v, u, 0}; ihead[v]=cnt;	}	ll isap(int s, int t, int n) {		for(int i=0; i<=n; ++i) d[i]=0, gap[i]=0, cur[i]=ihead[i];		gap[0]=n; int u=s, i, f; ll ret=0;		while(d[s]
     

　　

神题...在uoj群被神犇们吊打&裱

= =这么水的usaco training我都不会做= =

首先求最少边的话可以直接将权值变为$w*(m+1)+1$，然后就是最小割。理由很简单，最小割是$\sum_{i为一条割边} (w[i]*(m+1)+1) = (m+1)\sum_{i为一条割边} w[i] + c$首先我们分离出了原来没有改变权值的割，显然这样做$\sum_{i为一条割边} w[i]$是原图的最小割，因为乘上$(m+1)$后始终大于边数，和边数$c$都是常数= =。其次我们在求改变权值后的最小割后，比较完原图最小割后还比较了右边常数$c$，而$c$正是割边数。而$(m+1)$这个乘数也是因为割边数<=m最大可能到了m，可能会影响到原来图上的边权值，所以乘上$(m+1)$来消除影响。

那么现在问题变为求普通的字典序最少的最小割。我们考虑从小到大枚举边然后删边。

如果删掉$i$这条边时，最小割变小的值恰好为$i$改变后的权值，那么显然$i$是割边，此时维护的最小割减小，删掉$i$不恢复。

否则把删掉的边恢复。