考虑网络流求解这类分配问题。 建立源点 $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; }
题目2727 [USACO Open07]牛的进餐
AAAAAAAAAA
10
评论
2022-03-07 20:40:29
|
|
题目要求共有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. (第一次写题解,不足之处请大家多多包涵》_《)
题目1962 [HAOI 2015]树上染色
AAAAAAAAAA
5
评论
2022-03-01 19:52:22
|
|
题目3449 [USACO Feb06]特殊津贴
AAAAAAAAAA
3
评论
2021-12-22 21:40:34
|
|
Pro1697 人工湖 题解•【题目描述】 有一个湖,他的周围都是城市,每个城市都只和他相邻的两个城市有道路相连。假设有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!!!
题目1697 人工湖
AAAAAAAAAA
3
评论
2021-12-22 21:37:57
|
|
裸裸的区间DP。 我们定义f[l][r] 为卖掉l到r之间的临时得到的最大收益。 n[x]为第x个物品的价值。 Cl为第几天出售 转移方程就应该是f[l][r]=max(f[l+1][r]+cl*n[l],f[l][r+1]+cl*n[r]); 最后附上代码)
题目3449 [USACO Feb06]特殊津贴
AAAAAAAAAA
3
评论
2021-12-22 21:26:17
|
|
Pro2235 烤鸡翅 题解题目要求最大,观察数据范围,结合经验,考虑贪心。 当我们现在的烤鸡翅数量大于需求时,直接卖出。 否则,寻找前面已经卖出的最大的数量,如果该数大于当前需求,则用当前数目替代该数。 正确性不难证明:根据这个方法,我们遍历到第 $i$ 个人时,已经保证在不影响卖出人数的情况下让卖出的鸡翅数量最少。 再往后遍历时,也仍然可以保证。 这样,就实现了局部最优解向整体最优解的转变。 这个过程可以用大根堆实现。
题目2235 烤鸡翅
AAAAAAAAAA
13
评论
2021-12-22 13:22:58
|