The Exchange of Items

【题意】给出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;
}