——>>建图思路原来是这样子：设一个超级源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; }