【题意】给出N个项目,每个项目的数量有ai个,有M种交换,每次交换两个项目的一个数量,求最终使得每个项目数量为bi最小需要交换几次。
【题意】开始题意理解错, 以为是交换两个项目的值,唉,知道了这个题意还是很好做的,很容易想到费用流,把所有a[i]>b[i]的和源点连边,容量就是a[i]-b[i],费用0,反之和汇点相连,然后对于给出的M种交换,是无向边,所以两个方向都建边,容量INF,费用1,然后跑一边费用流就好了。
【AC CODE】0ms
#include <cstdio> #include <cstring> #include <cctype> #include <cmath> #include <set> //#include <unordered_set> #include <queue> #include <stack> #include <vector> #include <string> #include <algorithm> using namespace std; typedef long long LL; #define rep(i,a,n) for(int i = a; i < n; i++) #define repe(i,a,n) for(int i = a; i <= n; i++) #define per(i,n,a) for(int i = n; i >= a; i--) #define clc(a,b) memset(a,b,sizeof(a)) const int INF = 0x3f3f3f3f, MAXN = 100+10, MAXM = 300+10; struct ZKW_MinCostMaxFlow { private: int st, ed, ecnt, n; int head[MAXN],cap[MAXM<<1],cost[MAXM<<1],to[MAXM<<1],nxt[MAXM<<1]; int dis[MAXN]; void SPFA() { repe(i,0,n) dis[i] = INF; priority_queue<pair<int, int> > q; dis[st] = 0; q.push(make_pair(0, st)); while(!q.empty()){ int u = q.top().second, d = -q.top().first; q.pop(); if(dis[u] != d) continue; for(int p = head[u]; p!=-1; p = nxt[p]){ int &v = to[p]; if(cap[p] && dis[v] > d + cost[p]){ dis[v] = d + cost[p]; q.push(make_pair(-dis[v], v)); } } } repe(i,0,n) dis[i] = dis[ed] - dis[i]; } int minCost, maxFlow; bool use[MAXN]; int add_flow(int u, int flow) { if(u == ed) { maxFlow += flow; minCost += dis[st] * flow; return flow; } use[u] = true; int now = flow; for(int p = head[u]; p!=-1; p = nxt[p]) { int &v = to[p]; if(cap[p] && !use[v] && dis[u] == dis[v] + cost[p]) { int tmp = add_flow(v, min(now, cap[p])); cap[p] -= tmp; cap[p^1] += tmp; now -= tmp; if(!now) break; } } return flow - now; } bool modify_label() { int d = INF; repe(u,0,n) if(use[u]) for(int p = head[u]; p!=-1; p = nxt[p]) { int &v = to[p]; if(cap[p] && !use[v]) d = min(d, dis[v] + cost[p] - dis[u]); } if(d == INF) return false; repe(i,0,n) if(use[i]) dis[i] += d; return true; } public: void init() { clc(head,-1); ecnt = 2; } void add_edge(int u, int v, int cc, int ww) { cap[ecnt] = cc; cost[ecnt] = ww; to[ecnt] = v; nxt[ecnt] = head[u]; head[u] = ecnt++; cap[ecnt] = 0; cost[ecnt] = -ww; to[ecnt] = u; nxt[ecnt] = head[v]; head[v] = ecnt++; } int zkw(int ss, int tt, int nn, int &flow) { st = ss, ed = tt, n = nn; minCost = maxFlow = 0; SPFA(); while(true) { while(true) { repe(i,0,n) use[i] = 0; if(!add_flow(st, INF)) break; } if(!modify_label()) break; } flow = maxFlow; return minCost; } }zkwflow; int a[100+10],b[100+10]; int main() { #ifdef SHY freopen("d:\\1.txt", "r", stdin); #endif int n,m; while(~scanf("%d %d", &n, &m)) { int st = 0, ed = n+1, sum = 0,sum2 = 0, c = 0; zkwflow.init(); repe(i,1,n) { scanf("%d %d", &a[i], &b[i]), sum += a[i], sum2 += b[i]; if(a[i] > b[i]) zkwflow.add_edge(st,i,a[i]-b[i],0); if(b[i] > a[i]) zkwflow.add_edge(i,ed,b[i]-a[i],0), c += b[i]-a[i]; } rep(i,0,m) { int u,v; scanf("%d %d", &u, &v); zkwflow.add_edge(u,v,INF,1); zkwflow.add_edge(v,u,INF,1); } if(sum != sum2) { puts("-1"); continue; } int flow, ans = zkwflow.zkw(st,ed,ed,flow); if(flow != c) puts("-1"); else printf("%d\n",ans); } return 0; }