Alice's Chance poj1698 最大流

2019-11-06 07:58:29

字体：大中小

来源：转载

供稿：网友

Description

有n部电♂影，且每部电影至少要出演d天，这部电影可以拍w周，给出7个0或1的数字表示这一天能不能拍某电影，求是否能拍完所有电影

Code

网络流漏掉好多题(汗

开始想的是直接从原点连边到日期，结果发现这样是行不通的。于是加入一列点表示电影，从原点连一条边到电影节点容量为需要的天数

日期很容易想到是可以拆分的，那么7*50=350，算上20个电影的点370，那么我们只要开370*370的矩阵就行了

还有就是源点汇点的边最好一次性加完不然有重边的可能

神奇的地方在于不用矩阵会TLE，蒟蒻表示不懂求解释

Code

#include <stdio.h>#include <string.h>#include <queue>#define rep(i, st, ed) for (int i = st; i <= ed; i += 1)#define fill(x, t) memset(x, t, sizeof(x))#define N 372#define INF 0x3f3f3f3fusing namespace std;int rc[N][N], dis[N], v[10];inline void addEdge(int x, int y, int w){ rc[x][y] += w;}inline int bfs(int st, int ed){ fill(dis, -1); dis[st] = 1; queue<int>q; q.push(st); while (!q.empty()){ int now = q.front(); q.pop(); rep(i, 1, N - 1){ if (rc[now][i] > 0 && dis[i] == -1){ dis[i] = dis[now] + 1; q.push(i); if (i == ed){ return 1; } } } } return 0;}inline int min(int x, int y){ return x<y?x:y;}inline int find(int now, int mn, int ed){ if (now == ed || !mn){ return mn; } int ret = 0; rep(i, 1, N - 1){ if (rc[now][i] > 0 && dis[now] + 1 == dis[i]){ int d = find(i, min(rc[now][i], mn - ret), ed); rc[now][i] -= d; rc[i][now] += d; ret += d; if (ret == mn){ break; } } } return ret;}inline int dinic(int st, int ed){ int mxFlow = 0; while (bfs(st, ed)){ mxFlow += find(st, INF, ed); } return mxFlow;}int main(void){ int T; scanf("%d", &T); int ST = 0, ED = N - 1; while (T --){ int n; scanf("%d", &n); int d = 0; fill(rc, 0); rep(i, 1, n){ rep(j, 1, 7){ scanf("%d", &v[j]); } int tmpD, w; scanf("%d%d", &tmpD, &w); d += tmpD; addEdge(ST, i + 350, tmpD); rep(k, 0, w - 1){ rep(j, 1, 7){ if (v[j]){ addEdge(i + 350, k * 7 + j, 1); } } } } rep(i, 1, 350){ addEdge(i, ED, 1); } int ans = dinic(ST, ED); if (ans == d){ PRintf("Yes/n"); }else{ printf("No/n"); } } return 0;}

上一篇：MFC文件操作（CFile）

下一篇：c简单位操作