题目大意：给出一个图，每个边有权值。最后再给一条边。问最少去掉多少条边，可以使得这条新加的边既可能出现在最小生成树中，有可能出现在最大生成树中。
思路：先考虑最小生成树（最大的也一样）。若想这条边出现在最小生成树中，那么比这条边边权小的边一定不能将这条边的两点连起来，否则就不会选择这条边。所以就将所有的边权比这条边小的边建图，然后泡最小割，使得这两给点不连起来。这就是满足去掉最少的边让它出现在最小生成树。最大生成树就在建一张图，然后答案累加，就可以了。
CODE：
#include
#include
#include
#include
#include
#define MAX 400010 #define INF 0x7f7f7f7f #define S (add.x) #define T (add.y) using namespace std; struct Complex{ int x,y; int length; bool operator <(const Complex &a)const { return length < a.length; } void Read() { scanf("%d%d%d",&x,&y,&length); } }edge[MAX],add; int points,edges; int head[MAX],total = 1; int _next[MAX],aim[MAX],flow[MAX]; int ans; int deep[MAX]; inline void Add(int x,int y,int f); void Initialize(); bool BFS(); int Dinic(int x,int f); int main() { cin >> points >> edges; for(int i = 1;i <= edges; ++i) edge[i].Read(); add.Read(); sort(edge + 1,edge + edges + 1); for(int i = 1;edge[i].length < add.length; ++i) { Add(edge[i].x,edge[i].y,1); Add(edge[i].y,edge[i].x,1); } while(BFS()) ans += Dinic(S,INF); Initialize(); int start = 1; while(edge[start].length <= add.length) start++; for(int i = start;i <= edges; ++i) { Add(edge[i].x,edge[i].y,1); Add(edge[i].y,edge[i].x,1); } while(BFS()) ans += Dinic(S,INF); cout << ans << endl; return 0; } inline void Add(int x,int y,int f) { _next[++total] = head[x]; aim[total] = y; flow[total] = f; head[x] = total; } void Initialize() { total = 1; memset(head,0,sizeof(head)); } bool BFS() { static queue
q; while(!q.empty()) q.pop(); memset(deep,0,sizeof(deep)); deep[S] = 1; q.push(S); while(!q.empty()) { int x = q.front(); q.pop(); for(int i = head[x];i;i = _next[i]) if(!deep[aim[i]] && flow[i]) { deep[aim[i]] = deep[x] + 1; q.push(aim[i]); if(aim[i] == T) return true; } } return false; } int Dinic(int x,int f) { if(x == T) return f; int temp = f; for(int i = head[x];i;i = _next[i]) if(deep[aim[i]] == deep[x] + 1 && flow[i] && temp) { int away = Dinic(aim[i],min(flow[i],temp)); flow[i] -= away; flow[i^1] += away; temp -= away; } return f - temp; }