|
题意：有N个作业，M台机器，每个作业1天只能同1台机器运行，每台机器1天只能运行1个作业，第i个作业需要pi天完成，且只能从Si到Ei中选Pi天，问能否完成所有作业(T <= 20, N<=500, M<=200, 1 <= Pi, Si, Ei <= 500)。
——>>建图思路原来是这样子：设一个超级源s，每个作业为1个结点，从s往每个作业分别连1条边，容量为完成该作业所需的时间，那么从s发出满流时，就是作业所需天数，最后就看最大流是否为满流即可；作业可选择的天也分别作为1个结点，每个作业分别向其可选择的天连1条边，容量为1（因为每个作业1天只能同1台机器运行，每台机器1天只能运行1个作业）；最后，所有可选择的天分别向超级汇t连1条边，容量为M（因为每天最多只有M台机器）～ok～
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1000 + 10;
const int INF = 0x3f3f3f3f;
int N, M;
bool flag[maxn];
struct Edge{
int u, v, cap, flow;
Edge(int u = 0, int v = 0, int cap = 0, int flow = 0):
u(u), v(v), cap(cap), flow(flow){}
};
struct Dinic{
vector edges;
vector G[maxn];
int m, s, t;
int d[maxn], cur[maxn];
bool vis[maxn];
void addEdge(int u, int v, int cap){
edges.push_back(Edge(u, v, cap, 0));
edges.push_back(Edge(v, u, 0, 0));
m = edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
bool bfs(){
d[s] = 0;
memset(vis, 0, sizeof(vis));
queue qu;
qu.push(s);
vis[s] = 1;
while(!qu.empty()){
int u = qu.front(); qu.pop();
int sz = G[u].size();
for(int i = 0; i < sz; i++){
Edge& e = edges[G[u][i]];
if(!vis[e.v] && e.cap > e.flow){
d[e.v] = d[u] + 1;
vis[e.v] = 1;
qu.push(e.v);
}
}
}
return vis[t];
}
int dfs(int u, int a){
if(u == t || a == 0) return a;
int f, flow = 0;
int sz = G[u].size();
for(int i = cur[u]; i < sz; i++){
Edge& e = edges[G[u][i]];
cur[u] = i;
if(d[e.v] == d[u] + 1 && (f = dfs(e.v, min(a, e.cap-e.flow))) > 0){
e.flow += f;
edges[G[u][i]^1].flow -= f;
flow += f;
a -= f;
if(!a) break;
}
}
return flow;
}
int Maxflow(int s, int t){
this->s = s;
this->t = t;
int flow = 0;
while(bfs()){
memset(cur, 0, sizeof(cur));
flow += dfs(s, INF);
}
return flow;
}
};
int main()
{
int T, P, S, E, kase = 1;
scanf("%d", &T);
while(T--){
Dinic din;
scanf("%d%d", &N, &M);
memset(flag, 0, sizeof(flag));
int sum = 0;
for(int i = 1; i <= N; i++){
scanf("%d%d%d", &P, &S, &E);
din.addEdge(0, i, P);
for(int j = S; j <= E; j++){
din.addEdge(i, N+j, 1);
if(!flag[N+j]){
din.addEdge(N+j, 1001, M);
flag[N+j] = 1;
}
}
sum += P;
}
if(din.Maxflow(0, 1001) == sum) printf("Case %d: Yes\n\n", kase++);
else printf("Case %d: No\n\n", kase++);
}
return 0;
}
发现，以上的数据结构时空上都不如下面的数组写法：
#include
#include
#include
#include
using namespace std;
const int maxn = 1000 + 10;
const int maxm = 502000 + 10;
const int INF = 0x3f3f3f3f;
int head[maxn], nxt[maxm], ecnt, v[maxm], flow[maxm], cap[maxm];
bool flag[maxn];
int N, M;
struct Dinic{
int m, s, t;
int d[maxn], cur[maxn];
bool vis[maxn];
Dinic(){
memset(head, -1, sizeof(head));
ecnt = 0;
}
void addEdge(int uu, int vv, int ca){
v[ecnt] = vv; cap[ecnt] = ca; flow[ecnt] = 0; nxt[ecnt] = head[uu]; head[uu] = ecnt; ecnt++;
v[ecnt] = uu; cap[ecnt] = 0; flow[ecnt] = 0; nxt[ecnt] = head[vv]; head[vv] = ecnt; ecnt++;
}
bool bfs(){
d[s] = 0;
memset(vis, 0, sizeof(vis));
queue qu;
qu.push(s);
vis[s] = 1;
while(!qu.empty()){
int u = qu.front(); qu.pop();
for(int e = head[u]; e != -1; e = nxt[e]){
if(!vis[v[e]] && cap[e] > flow[e]){
d[v[e]] = d[u] + 1;
vis[v[e]] = 1;
qu.push(v[e]);
}
}
}
return vis[t];
}
int dfs(int u, int a){
if(u == t || a == 0) return a;
int f, Flow = 0;
for(int e = cur[u]; e != -1; e = nxt[e]){
cur[u] = e;
if(d[v[e]] == d[u] + 1 && (f = dfs(v[e], min(a, cap[e]-flow[e]))) > 0){
flow[e] += f;
flow[e^1] -= f;
Flow += f;
a -= f;
if(!a) break;
}
}
return Flow;
}
int Maxflow(int s, int t){
this->s = s;
this->t = t;
int Flow = 0;
while(bfs()){
memcpy(cur, head, sizeof(head));
Flow += dfs(s, INF);
}
return Flow;
}
};
int main()
{
int T, P, S, E, kase = 1;
scanf("%d", &T);
while(T--){
Dinic din;
scanf("%d%d", &N, &M);
memset(flag, 0, sizeof(flag));
int sum = 0;
for(int i = 1; i <= N; i++){
scanf("%d%d%d", &P, &S, &E);
din.addEdge(0, i, P);
for(int j = S; j <= E; j++){
din.addEdge(i, N+j, 1);
if(!flag[N+j]){
din.addEdge(N+j, 1001, M);
flag[N+j] = 1;
}
}
sum += P;
}
if(din.Maxflow(0, 1001) == sum) printf("Case %d: Yes\n\n", kase++);
else printf("Case %d: No\n\n", kase++);
}
return 0;
}
|