题目数据规模不大，可选方法很多，考虑贪心。

本文中，称第 $i$ 行/列 的要求士兵数量为：第 $i$ 行/列 的名额。

很显然，对于第 $i$ 行第 $j$ 列的士兵，如果它可以放，并且能一次性占掉第 $i$ 行和第 $j$ 列的两个名额，称这样的士兵为 ”好士兵“。

根据贪心思路，我们当然希望“好士兵”的个数尽量的多，那么剩下的未被占掉的名额自然只能由一次性只占一个名额的士兵占掉。

那么：怎样让“好士兵”最多呢？

由题目可知，第 $i$ 行/列 的“好士兵”个数不能超过该 行/列 的名额总数。

这一点和网络流的容量限制很像，联想到网络流，进行建模：

设第 $i$ 行名额数为 $A_i$，对应点 $C_i$，第 $j$ 列名额数为 $B_j$，对应点 $D_j$。

分别建立两个顶点：起点 $S$，终点 $T$。

$S$ 向每个 $C_i$ 连一条容量为 $A_i$ 的边，每个 $D_j$ 向 $T$ 连一条容量为 $B_j$ 的边。

如果 $(i,j)$ 合法，由 $C_i$ 向 $D_j$ 引一条容量为 $1$ 的边。

这样，$S \to C_i \to D_j \to T$ 的一条路径就代表了 $(i,j)$ 上放置一名“好士兵”。

该图的最大流对应的即是最多的可放置的“好士兵”的个数，设为 $F$ ，则答案为

$\sum\limits_{i=1}^n A_i + \sum\limits_{j=1}^m B_j - F$

参考代码：

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,k;
const int maxn = 10005;
const int maxm = 1000005;
int L[maxn],R[maxn],sum1[maxn],sum2[maxn],tot;
bool legit[maxn][maxn];
int head[maxm],ver[maxm << 1],nxt[maxm << 1],cap[maxm << 1],cur[maxm],cnt = -1;
void add(int u,int v,int t) {
	ver[++ cnt] = v;
	nxt[cnt] = head[u];
	head[u] = cnt;
	cap[cnt] = t;
	return ;
}
queue<int> q;
int level[maxn];
bool bfs(int s,int t) {
	memset(level , 0 , sizeof(level));
	q.push(s);
	level[s] = 1;
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(int i = head[u];~ i;i = nxt[i]) {
			int v = ver[i];
			if(cap[i]&&!level[v]) {
				level[v] = level[u] + 1;
				q.push(v);
			}
		}
	}
	return level[t] > 0;
} 
int dfs(int x,int t,int maxflow) {
	if(x == t||!maxflow)return maxflow;
	int flow = 0,f;
	for(int& i = cur[x];~ i;i = nxt[i]) {
		int v = ver[i];
		if(level[v] == level[x] + 1&&(f = dfs(v , t , min(maxflow , cap[i])))) {
			if(!f) {
				level[v] = 0;
				break ;
			}
			flow += f;
			maxflow -= f;
			cap[i] -= f;
			cap[i ^ 1] += f;
			if(!maxflow)break ;
		}
	}
	return flow;
}
int Dinic(int s,int t) {
	int flow = 0;
	while(bfs(s , t)) {
		memcpy(cur , head , sizeof(head));
		flow += dfs(s , t , 0x3f3f3f3f);
	}
	return flow;
}
int main() {
	freopen("occupy.in","r",stdin);
	freopen("occupy.out","w",stdout);
	memset(head , -1 , sizeof(head));
	scanf("%d%d%d",&n,&m,&k);
	for(int i = 1;i <= n;++ i)
		for(int j = 1;j <= m;++ j)legit[i][j] = true;
	for(int i = 1;i <= n;++ i)scanf("%d",&L[i]),sum1[i] = m,tot += L[i];
	for(int i = 1;i <= m;++ i)scanf("%d",&R[i]),sum2[i] = n,tot += R[i];
	for(int i = 1;i <= k;++ i) {
		int x,y;
		scanf("%d%d",&x,&y);
		legit[x][y] = false;
		-- sum1[x];
		-- sum2[y];
	}
	bool flag = true;
	for(int i = 1;i <= n;++ i) {
		if(sum1[i] < L[i]) {
			flag = false;
			break ;
		} 
	}
	for(int i = 1;i <= m;++ i) {
		if(sum2[i] < R[i]) {
			flag = false;
			break ;
		}
	}
	if(!flag) {
		puts("JIONG!");
		return 0;
	}
	int S = n + m + 1,T = n + m + 2;
	for(int i = 1;i <= n;++ i) {
		add(S , i , L[i]);
		add(i , S , 0);
	}
	for(int i = 1;i <= m;++ i) {
		add(i + n , T , R[i]);
		add(T , i + n , 0);
	}
	for(int i = 1;i <= n;++ i) {
		for(int j = 1;j <= m;++ j) {
			if(legit[i][j]) {
				add(i , j + n , 1);
				add(j + n , i , 0);
			}
		}
	}
	printf("%d\n",tot - Dinic(S , T));
	return 0;
}

建图：源点->食物->牛->牛->饮料->汇点

边权都是1

跑最大流

然后就A了

考虑网络流求解这类分配问题。

建立源点 $S$，汇点 $T$。令从 $S$ 到 $T$ 的一条路径表示一个奶牛得到了喜欢的食物和饮料。

显然需要对每个食物 $i$ 建立点 $f_i$，对饮料 $j$ 建立点 $d_j$。

食物的点集和饮料的点集显然不能同时连向源点 $S$，不妨对于每个 $f_i,d_j$ 建立 $S \to f_i$ 和 $d_j \to T$ 的容量为 $1$ 的有向边。

如果每个奶牛直接和食物和饮料的集合连边，那么很可能会出现同一个奶牛同时享有多种食物和饮料的情况，然而这时奶牛对最大流的贡献仅为 $1$，求出的最大流却有可能很大。

考虑对其进行限制。对于每个奶牛，建立两个点，两点间连一条容量为 $1$ 的边，这两个点再分别与喜欢的食物和饮料相连，这样就能保证同一个奶牛至多满足一次。

最后直接在建出的图上跑最大流即可。

（代码很丑，见谅）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 20005;
int ver[maxn << 1],nxt[maxn << 1],cap[maxn << 1],head[maxn];
int cnt = -1;
int cur[maxn],level[maxn];
queue <int> q; 
void add(int u,int v,int t) {
    nxt[++ cnt] = head[u];
    ver[cnt] = v;
    cap[cnt] = t;
    head[u] = cnt;
    return ;
}
void AddEdge(int u,int v) {
    add(u , v , 1);
    add(v , u , 0);
    return ;
}
int n;
bool bfs(int s,int t) {
    memset(level , 0 , sizeof(level));
    q.push(s);
    level[s] = 1;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = head[u];~ i;i = nxt[i]) {
            int v = ver[i];
            if(!level[v]&&cap[i]) {
                level[v] = level[u] + 1;
                q.push(v);
            }
        }
    }
    return level[t] != 0;
}
int dfs(int x,int t,int maxflow) {
    if(x == t||!maxflow)return maxflow;
    int flow = 0,f;
    for(int& i = cur[x];~ i;i = nxt[i]) {
        int v = ver[i];
        if(level[v] == level[x] + 1&&(f = dfs(v , t , min(maxflow , cap[i])))) {
            if(!f) {
                level[v] = 0;
                break ;
            }
            flow += f;
            maxflow -= f;
            cap[i] -= f;
            cap[i ^ 1] += f;
            if(!maxflow)break;
        }
    }
    return flow;
}
int Dinic(int s,int t) {
    int flow = 0;
    while(bfs(s , t)) {
        memcpy(cur , head , sizeof(cur));
        flow += dfs(s , t , 0x3f3f3f3f);
    }
    return flow;
}
int S,T,tot,f[maxn],d[maxn],F,D,c1[maxn],c2[maxn];
int main() {
    freopen("usaco_open07_dining.in","r",stdin);
    freopen("usaco_open07_dining.out","w",stdout);
    scanf("%d%d%d",&n,&F,&D);
    memset(head , -1 , sizeof(head));
    S = ++ tot;
    T = ++ tot;
    for(int i = 1;i <= F;++ i)f[i] = ++ tot,AddEdge(S , f[i]);
    for(int i = 1;i <= D;++ i)d[i] = ++ tot,AddEdge(d[i] , T);
    for(int i = 1;i <= n;++ i)c1[i] = ++ tot,c2[i] = ++ tot,AddEdge(c1[i] , c2[i]);
    for(int i = 1;i <= n;++ i) {
        int x,y,z;
        scanf("%d%d",&x,&y);
        for(int j = 1;j <= x;++ j) {
            scanf("%d",&z);
            AddEdge(f[z] , c1[i]);
        }
        for(int j = 1;j <= y;++ j) {
            scanf("%d",&z);
            AddEdge(c2[i] , d[z]);
        }
    }
    printf("%d\n",Dinic(S , T));
    fclose(stdin);
    fclose(stdout);
    return 0;
}

题目要求共有n个结点，将其中k个点染成黑色（本题解中为了方便描述，通称所有未染色的点为白点），求黑点两两距离及白点两两距离，使他们之和最大。

我们可以将距离转化为路径，然后再将路径拆分成边，就可以记录每条边被经过的次数，直接计算即可。

问题来了！：那么每条边会对答案贡献多少呢？

我们不妨设这条边的一侧共有w个点，其中有t个点被染成黑色了；

那么这一侧共有t个黑点，（w-t）个白点；类似，另一侧有（k-t）个黑点，（n-w-k+t）个白点；

令sz为这条边的边权，那么贡献就是val=sz*(t*(k-t)+(w-t)*(n-w-k+t));

解题的大致思路就是计算每条边对答案的贡献，最后利用状态转移方程求出最优解。

首先给出状态数组：f[x][y];

f[x][y]表示给以x为根结点的子树染上y个点所得的对于整棵树的最大贡献；

方程如下：

f[i][j]=max(f[i][j],f[i][j-t]+f[z][t]+val);(z表示i的子结点)

目标状态：f[1][k];

最后附上代码

PS:中间可能遇到非法情况，建议把f[x][y]预处理成非法情况，方便跳过处理（代码最后有针对这点的样例，可自行调试）；

强烈建议参考代码理解！！！！！

Over.

(第一次写题解，不足之处请大家多多包涵》_《)

•【题目描述】

有一个湖，他的周围都是城市，每个城市都只和他相邻的两个城市有道路相连。假设有n个城市，编号1-n，公路是双向的，公路有时候是好的，有时候是坏的，现在询问你两个城市是否可以互相到达。

•【输入格式】

第一行两个数，一个2<=n<=100000  和 1<=m<=100000，分别代表城市数目和询问次数；

接下来m行，每一行三个数f，a，b。f=0时，如果公路a，b之间的道路之前是好的，现在就变成坏的，如果之前是坏的，现在就变成好的。f=1时，询问a，b两个城市是否可以互相到达。

•【输出格式】

对于每一个f=1的询问，能到达输出“YES”，否则输出"NO".

思路如下：

首先，我们可以设g[x]数组表示x号城市与x+1号城市之间的道路好坏情况：g[x]=1时表示坏，g[x]=0时表示好，同时设sz为坏的道路的个数。

因为所有城市围起来形成一个圆，规定x到（x+1）号城市为顺时针方向，x到（x-1）号城市为逆时针方向。

我们来谈谈f=1时，即判断a、b两城市是否可以到达（预处理使a<b）。

那么在判断a、b两城市是否可以到达时，我们只需考虑两种情况：

（1）：沿顺时针道路判断是否可以到达

令G=g[a]+g[a+1]+g[a+2]+……+g[b-1]（即a沿顺时针到b间的路径间坏的道路的个数）很明显，我们只需判断G是否>=1。若是，则表示a沿顺时针到b之间的路径有坏的道路，不能从a顺时针到达b。

（2）：沿逆时针道路判断是否可以到达

其实思路也不难想出，我们可以简单地处理出sz（即坏的道路的个数），若sz-G=0，

即表示除a沿顺时针到b的路径间坏的道路外，没有坏的道路，这就等同于a沿逆时针到b的路径间没有坏的道路，可以从a到b。

反之（sz-G不为0）则表示a沿逆时针到b之间的路径有坏的道路，不能从a顺时针到达b。

好了，现在你已经了解了这题的大致思路了，那么就尝试AC吧！！！（不是

以上思路大家肯定都想到了（所以以上都是废话），那么我们开始优化时间吧！

我们懂得，若按照以上思路暴力求解，那么时间复杂度为O(nm)，只能拿到50pts

接下来考虑100pts算法

我们可以发现g是一维数组，求G为g的区间求和，那么很自然的就联想到树状数组

设树状数组f[x]表示坏的道路的个数， G=g[a]+g[a+1]+g[a+2]+…… +g[b-1] =求和f(b-1)-求和f(a-1）

然后1与n号城市间的道路做个特殊处理。

最后推荐大家参考代码理解（COGS代码已开放）

Over!!!