网络流

hdu3572

题意：n件工作，m个机器，一个机器一个时间只能给一个工作使用，每件工作i必须在si[i]~ei[i]之间选pi[i]个时间，问是否可以满足条件。

刚开始把每个时间每个机器都当成一个点，没有m能当流量的概念，想不到其实对于可以再这一天进行的工作来说不管在哪个机器上都是无所谓的，

所以把工作，时间当成点，该工作能在该时间工作就连流量为1，源点到工作连该工作需要的时间，时间当汇点流量为机器的个数，满流就Yes；

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<iostream>
  5 #include<cmath>
  6 #include<algorithm>
  7 #include<vector>
  8 #include<queue>
  9 using namespace std;
 10 const int maxn = 1000+1000;
 11 const int N = 500+10;
 12 const int INF = 1000000000+10;
 13 struct Edge{
 14     int from, to, cap, flow;
 15     Edge(){}
 16     Edge(int a,int b,int c,int d):from(a),to(b),cap(c),flow(d) {}
 17 
 18 };
 19 vector<Edge> edges;
 20 vector<int> G[maxn];
 21 struct Dinic { // O(n^2m)
 22 
 23 
 24 
 25     int m, s, t;
 26     bool vis[maxn];
 27     int d[maxn];
 28     int cur[maxn];
 29     void init(){
 30         edges.clear();
 31         for (int i = 0; i < maxn; i++) G[i].clear();
 32     }
 33     void AddEdge(int from, int to, int cap) {
 34         edges.push_back(Edge(from, to, cap, 0));
 35         edges.push_back(Edge(to, from, 0, 0));
 36         m = edges.size();
 37         G[from].push_back(m-2);
 38         G[to].push_back(m-1);
 39     }
 40     bool BFS(){
 41         memset(vis, 0, sizeof(vis));
 42         queue<int> Q;
 43         Q.push(s);
 44         d[s] = 0;
 45         vis[s] = 1;
 46         while (!Q.empty()) {
 47             int x = Q.front(); Q.pop();
 48             for (int i = 0; i < (int)G[x].size(); i++) {
 49                 Edge& e = edges[G[x][i]];
 50                 if (!vis[e.to] && e.cap > e.flow) {
 51                     vis[e.to] = 1;
 52                     d[e.to] = d[x] + 1;
 53                     Q.push(e.to);
 54                 }
 55             }
 56         }
 57         return vis[t];
 58     }
 59 
 60     int DFS(int x,int a) {
 61         if (x == t || a == 0) return a;
 62         int flow = 0, f;
 63         for (int& i = cur[x]; i < (int)G[x].size(); i++) {
 64             Edge& e = edges[G[x][i]];
 65             if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
 66                 e.flow += f;
 67                 edges[G[x][i]^1].flow -= f;
 68                 flow += f;
 69                 a -= f;
 70                 if (a == 0) break;
 71             }
 72         }
 73         return flow;
 74     }
 75     int Maxflow(int s,int t) {
 76         this->s = s; this->t = t;
 77         int flow = 0;
 78         while (BFS()) {
 79             memset(cur, 0, sizeof(cur));
 80             flow += DFS(s, INF);
 81         }
 82         return flow;
 83     }
 84 }Rabbit;
 85 int n, m;
 86 int pi[N],si[N],ei[N];
 87 int main(){
 88     int T, cas = 0;
 89     scanf("%d",&T);
 90     while (T--) {
 91         scanf("%d%d",&n,&m);
 92         int sum = 0, tmp = 0;
 93         for (int i = 0; i < n; i++) {
 94             scanf("%d%d%d",pi+i,si+i,ei+i);
 95             sum += pi[i];
 96             tmp = max(tmp, ei[i]);
 97         }
 98         Rabbit.init();
 99         int cnt = 2+n;
100         for (int i = 0; i < n; i++) {
101             Rabbit.AddEdge(0, 2+i, pi[i]);
102         }
103         for (int i = 0; i < n; i++) {
104             for (int j = si[i]; j <= ei[i]; j++) {
105                 Rabbit.AddEdge(2+i, 2+n+j, 1);
106             }
107         }
108         for (int i = 1; i <= tmp; i++) Rabbit.AddEdge(2+n+i, 1, m);
109         printf("Case %d: ",++cas);
110         if (Rabbit.Maxflow(0, 1) == sum) puts("Yes");
111         else puts("No");
112         puts("");
113     }
114     return 0;
115 }

View Code

hdu2883

跟上题差不多，但是时间范围很大，需要合并，（为什么可以合并，因为连到该时间间隔的工作都是可以在该时间间隔内的任意时间工作）；注意题目的时间从si~ti只有ti-si时间；

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<iostream>
  5 #include<cmath>
  6 #include<algorithm>
  7 #include<vector>
  8 #include<queue>
  9 #define foreach(it,a) for(__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
 10 
 11 using namespace std;
 12 
 13 const int maxn = 1000+1000;
 14 const int N = 200+10;
 15 const int INF = 1000000000+10;
 16 struct Edge{
 17     int from, to, cap, flow;
 18     Edge(){}
 19     Edge(int a,int b,int c,int d):from(a),to(b),cap(c),flow(d) {}
 20 
 21 };
 22 vector<Edge> edges;
 23 vector<int> G[maxn];
 24 struct Dinic {
 25 
 26 
 27 
 28     int m, s, t;
 29     bool vis[maxn];
 30     int d[maxn];
 31     int cur[maxn];
 32     void init(){
 33         edges.clear();
 34         for (int i = 0; i < maxn; i++) G[i].clear();
 35     }
 36     void AddEdge(int from, int to, int cap) {
 37         edges.push_back(Edge(from, to, cap, 0));
 38         edges.push_back(Edge(to, from, 0, 0));
 39         m = edges.size();
 40         G[from].push_back(m-2);
 41         G[to].push_back(m-1);
 42     }
 43     bool BFS(){
 44         memset(vis, 0, sizeof(vis));
 45         queue<int> Q;
 46         Q.push(s);
 47         d[s] = 0;
 48         vis[s] = 1;
 49         while (!Q.empty()) {
 50             int x = Q.front(); Q.pop();
 51             for (int i = 0; i < (int)G[x].size(); i++) {
 52                 Edge& e = edges[G[x][i]];
 53                 if (!vis[e.to] && e.cap > e.flow) {
 54                     vis[e.to] = 1;
 55                     d[e.to] = d[x] + 1;
 56                     Q.push(e.to);
 57                 }
 58             }
 59         }
 60         return vis[t];
 61     }
 62 
 63     int DFS(int x,int a) {
 64         if (x == t || a == 0) return a;
 65         int flow = 0, f;
 66         for (int& i = cur[x]; i < (int)G[x].size(); i++) {
 67             Edge& e = edges[G[x][i]];
 68             if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
 69                 e.flow += f;
 70                 edges[G[x][i]^1].flow -= f;
 71                 flow += f;
 72                 a -= f;
 73                 if (a == 0) break;
 74             }
 75         }
 76         return flow;
 77     }
 78     int Maxflow(int s,int t) {
 79         this->s = s; this->t = t;
 80         int flow = 0;
 81         while (BFS()) {
 82             memset(cur, 0, sizeof(cur));
 83             flow += DFS(s, INF);
 84         }
 85         return flow;
 86     }
 87 }Rabbit;
 88 vector<int> vti;
 89 int n, m;
 90 int si[N], ei[N], ni[N], ti[N];
 91 int main(){
 92 
 93     while (~scanf("%d%d",&n,&m)) {
 94         vti.clear();
 95         int sum = 0;
 96         for (int i = 0; i < n; i++) {
 97             scanf("%d%d%d%d",si+i, ni+i, ei+i, ti+i);
 98             vti.push_back(si[i]);
 99             vti.push_back(ei[i]);
100             sum += ni[i] * ti[i];
101         }
102         sort(vti.begin(), vti.end());
103         vti.erase(unique(vti.begin(), vti.end()), vti.end());
104         /*foreach(it,vti)
105             cout<<*it<<" ";cout<<endl;
106         */Rabbit.init();
107         for (int i = 0; i < n; i++) {
108             Rabbit.AddEdge(0, 2+i, ni[i] * ti[i]);
109         }
110         for (int i = 0; i < n; i++) {
111             for (int j = 0; j < (int)vti.size() - 1; j++) {
112                 if (si[i] <= vti[j] && vti[j+1] <= ei[i])
113                     Rabbit.AddEdge(2+i, 2+n+j, INF);
114             }
115         }
116         for (int i = 0; i < (int)vti.size()-1; i++) Rabbit.AddEdge(2+n+i, 1, (vti[i+1] - vti[i]) * m);
117         if (Rabbit.Maxflow(0, 1) == sum) puts("Yes");
118         else puts("No");
119     }
120     return 0;
121 }

View Code