[hdu3572]最大流(dinic)

题意：有m台机器，n个任务，每个任务需要在第si~ei天之间，且需要pi天才能完成，每台机器每天只能做一个任务，不同机器每天不能做相同任务，判断所有任务是否可以做完。

思路：把影响答案的对象提取出来，得到以下几个：机器，任务，时间；需要用一个量把这三者联系起来，不难想到用工作量来表示。从源点向每个任务连一条容量为pi的有向边，表示这个任务需要pi个工作量才能完成，从每个任务向第si天到第ei天各连一条容量为1的有向边，表示这个任务可以在第si天到第ei天的任意一天“消耗”1个工作量，或者说第si天到第ei天的任意一天都可以花一个工作量来做这个工作，从每一天向汇点连一条容量为m的边，表示每一天允许产生m个工作量（m台机器每天产生m个工作量）。跑一遍最大流，看最大流是否等于所有任务的pi的和即可。

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

/* ******************************************************************************** */

#include <iostream>                                                                 //

#include <cstdio>                                                                   //

#include <cmath>                                                                    //

#include <cstdlib>                                                                  //

#include <cstring>                                                                  //

#include <vector>                                                                   //

#include <ctime>                                                                    //

#include <deque>                                                                    //

#include <queue>                                                                    //

#include <algorithm>                                                                //

#include <map>                                                                      //

using namespace

std;

//

#define pb push_back                                                                //

#define mp make_pair                                                                //

#define X first                                                                     //

#define Y second                                                                    //

#define all(a) (a).begin(), (a).end()                                               //

#define foreach(a, i) for (typeof(a.begin()) i = a.begin(); i != a.end(); ++ i) //

#define fill(a, x) memset(a, x, sizeof(a))                                          //

//

void RI(vector<int>&a,int n){a.resize(n);for(int i=0;i<n;i++)scanf("%d",&a[i]);} //

void RI(){}void RI(int&X){scanf("%d",&X);}template<typename...R> //

void RI(int&f,R&...r){RI(f);RI(r...);}void RI(int*p,int*q){int d=p<q?1:-1; //

while(p!=q){scanf("%d",p);p+=d;}}void print(){cout<<endl;}template<typename T> //

void print(const T t){cout<<t<<endl;}template<typename F,typename...R> //

void print(const F f,const R...r){cout<<f<<", ";print(r...);}template<typename T> //

void print(T*p, T*q){int d=p<q?1:-1;while(p!=q){cout<<*p<<", ";p+=d;}cout<<endl;} //

//

typedef pair<int, int

> pii;

//

typedef long long

ll;

//

typedef unsigned long long ull; //

//

template<typename T>bool umax(T&a, const T&b){return b>a?false:(a=b,true);} //

template<typename T>bool umin(T&a, const T&b){return b<a?false:(a=b,true);} //

template<typename

T>

//

void V2A(T a[],const vector<T>&b){for(int i=0;i<b.size();i++)a[i]=b[i];} //

template<typename

T>

//

void A2V(vector<T>&a,const T b[]){for(int i=0;i<a.size();i++)a[i]=b[i];} //

//

/* -------------------------------------------------------------------------------- */

struct Dinic {

private:

const static int maxn = 1e3 + 7;

struct Edge {

int from, to, cap;

Edge(int u, int v, int w): from(u), to(v), cap(w) {}

};

int s, t;

vector<Edge> edges;

vector<int> G[maxn];

bool vis[maxn];

int d[maxn], cur[maxn];

bool bfs() {

memset(vis, 0, sizeof(vis));

queue<int> Q;

Q.push(s);

d[s] = 0;

vis[s] = true;

while (!Q.empty()) {

int x = Q.front(); Q.pop();

for (int i = 0; i < G[x].size(); i ++) {

Edge &e = edges[G[x][i]];

if (!vis[e.to] && e.cap) {

vis[e.to] = true;

d[e.to] = d[x] + 1;

Q.push(e.to);

}

return vis[t];

}

int dfs(int x, int a) {

if (x == t || a == 0) return a;

int flow = 0, f;

for (int &i = cur[x]; i < G[x].size(); i ++) {

Edge &e = edges[G[x][i]];

if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap))) > 0) {

e.cap -= f;

edges[G[x][i] ^ 1].cap += f;

flow += f;

a -= f;

if (a == 0) break;

}

return flow;

}

public:

void clear() {

for (int i = 0; i < maxn; i ++) G[i].clear();

edges.clear();

memset(d, 0, sizeof(d));

}

void add(int from, int to, int cap) {

edges.push_back(Edge(from, to, cap));

edges.push_back(Edge(to, from, 0));

int m = edges.size();

G[from].push_back(m - 2);

G[to].push_back(m - 1);

}

int solve(int s, int t) {

this->s = s; this->t = t;

int flow = 0;

while (bfs()) {

memset(cur, 0, sizeof(cur));

flow += dfs(s, 1e9);

}

return flow;

}

};

Dinic solver;

const int maxn = 507;

int p[maxn], s[maxn], e[maxn];

int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif // ONLINE_JUDGE

int T, n, m, cas = 0;

cin >> T;

while (T --) {

cin >> n >> m;

solver.clear();

int total = 0;

for (int i = 1; i <= n; i ++) {

scanf("%d%d%d", p + i, s + i, e + i);

total += p[i];

}

for (int i = 1; i <= n; i ++) {

solver.add(0, i, p[i]);

for (int j = s[i]; j <= e[i]; j ++) {

solver.add(i, n + j, 1);

}

for (int i = 1; i <= 500; i ++) solver.add(n + i, n + 501, m);

printf("Case %d: ", ++ cas);

puts(solver.solve(0, n + 501) == total? "Yes" : "No");

puts("");

}

return

0;

//

/* ******************************************************************************** */

巴特西

[hdu3572]最大流(dinic)

最新文章

热门文章