Description
Our geometry princess XMM has stoped her study in computational geometry to concentrate on her newly opened factory. Her factory has introduced M new machines in order to process the coming N tasks. For the i-th task, the factory has to start processing it at or after day Si, process it for Pi days, and finish the task before or at day Ei. A machine can only work on one task at a time, and each task can be processed by at most one machine at a time. However, a task can be interrupted and processed on different machines on different days.
Now she wonders whether he has a feasible schedule to finish all the tasks in time. She turns to you for help.
Now she wonders whether he has a feasible schedule to finish all the tasks in time. She turns to you for help.
Input
On the first line comes an integer T(T<=20), indicating the number of test cases.
You are given two integer N(N<=500) and M(M<=200) on the first line of each test case. Then on each of next N lines are three integers Pi, Si and Ei (1<=Pi, Si, Ei<=500), which have the meaning described in the description. It is guaranteed that in a feasible schedule every task that can be finished will be done before or at its end day.
You are given two integer N(N<=500) and M(M<=200) on the first line of each test case. Then on each of next N lines are three integers Pi, Si and Ei (1<=Pi, Si, Ei<=500), which have the meaning described in the description. It is guaranteed that in a feasible schedule every task that can be finished will be done before or at its end day.
Output
For each test case, print “Case x: ” first, where x is the case number. If there exists a feasible schedule to finish all the tasks, print “Yes”, otherwise print “No”.
Print a blank line after each test case.
Print a blank line after each test case.
Sample Input
2
4 3
1 3 5
1 1 4
2 3 7
3 5 9
2 2
2 1 3
1 2 2
Sample Output
Case 1: Yes
Case 2: Yes
题意：给n个任务和m台机器，每个任务有三个值，s e p表示这个完成这个任务需要p天，并且这p天要在s到e这段时间完成（包括s和e），任务可以中断再换台机器换一天来继续做，每台机器每天只能完成一个任务，而且一个任务每天只能给一台机器来做
思路：最大流。建图方法是， 把每个任务当成一个点，每个时间点也当成一个点，源点连接每个任务容量为p，每个任务连接每个时间点容量为1，每个时间点连接汇点容量为m，然后判断最大流是否和p点总和相等
妈蛋啊，这题卡了不少天，还以为是各种模板错了，原来所因为给每个时间点连汇点点时候for循环用i但是下面却用了j我擦擦擦卡勒那么多天，都换了几个模板来做了。。
AC代码： 1.白书dinic模板 2.白书ISAP模板 3.网上的dinic模板 4.网上ISAP模板
1和2跑了350ms 3跑了78ms 4跑了109ms
1. 359ms
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int INF = 1e9; const double eps = 1e-6; const int maxn = 1010; int cas = 1; struct Edge{ int from,to,cap,flow; Edge() {} Edge(int a,int b,int c,int d) { from=a,to=b,cap=c,flow=d; } }; struct Dinic{ int n,m,s,t; vector<Edge> edges; vector<int> G[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; void AddEdge(int from,int to,int cap) { edges.push_back(Edge(from,to,cap,0)); edges.push_back(Edge(to,from,0,0)); m=edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } void init(int x) { memset(d,0,sizeof(d)); edges.clear(); for(int i=0;i<=x;i++) G[i].clear(); } bool BFS() { memset(vis,0,sizeof(vis)); queue<int> Q; Q.push(s); d[s]=0; vis[s]=1; 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>e.flow) { vis[e.to]=1; 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-e.flow)))>0) { e.flow += f; edges[G[x][i]^1].flow -= f; flow += f; a -= f; if(a==0) 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; } }; Dinic dinic; int n,m; inline int id_task(int x) {return x;} inline int id_time(int x) {return x+500;} int s = 0, t = 1001; void run() { scanf("%d%d",&n,&m); dinic.init(1001); int i,j; int a,b,c; int sum=0; for(i=1;i<=n;i++) { scanf("%d%d%d",&c,&a,&b); sum+=c; dinic.AddEdge(s,id_task(i),c); for(j=a;j<=b;j++) dinic.AddEdge(id_task(i),id_time(j),1); } for(i=1;i<=500;i++) dinic.AddEdge(id_time(i),t,m); // printf("%d ",dinic.Maxflow(0,500+500+1)); printf("Case %d: %s ",cas++,dinic.Maxflow(s,t)==sum?"Yes":"No"); } int main() { #ifdef LOCAL freopen("in","r",stdin); #endif int _; scanf("%d",&_); while(_--) run(); return 0; }
2. 343ms
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> #define FOR(i,n) for(i=0;i<=(n);i++) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int INF = 1e9; const double eps = 1e-6; const int maxn = 1010; const int N = 1010; int cas = 1; struct Edge{ int from,to,cap,flow; Edge() {} Edge(int a,int b,int c,int d) { from=a,to=b,cap=c,flow=d; } }; struct ISAP{ int n,m,s,t; int p[N],num[N]; vector<Edge> edges; vector<int> G[N]; bool vis[N]; int d[N],cur[N]; void init(int _n) { n=_n; int i; edges.clear(); FOR(i,n) { G[i].clear(); d[i]=INF; } } void AddEdge(int from,int to,int cap) { edges.push_back(Edge(from,to,cap,0)); edges.push_back(Edge(to,from,0,0)); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS() { memset(vis,0,sizeof(vis)); queue<int> Q; Q.push(t); d[t]=0; vis[t]=1; while(!Q.empty()) { int x = Q.front(); Q.pop(); for(unsigned i=0;i<G[x].size();i++) { Edge& e = edges[G[x][i]^1]; if(!vis[e.from] && e.cap>e.flow) { vis[e.from]=1; d[e.from] = d[x]+1; Q.push(e.from); } } } return vis[s]; } int Augment() { int x=t, a=INF; while(x!=s) { Edge& e = edges[p[x]]; a = min(a,e.cap-e.flow); x = edges[p[x]].from; } x = t; while(x!=s) { edges[p[x]].flow+=a; edges[p[x]^1].flow-=a; x=edges[p[x]].from; } return a; } int Maxflow(int _s,int _t) { s=_s; t=_t; int flow = 0, i; BFS(); if(d[s]>=n) return 0; memset(num,0,sizeof(num)); memset(p,0,sizeof(p)); FOR(i,n) if(d[i]<INF) num[d[i]]++; int x=s; memset(cur,0,sizeof(cur)); while(d[s]<n) { if(x==t) { flow+=Augment(); x=s; } int ok=0; for(unsigned i=cur[x];i<G[x].size();i++) { Edge& e=edges[G[x][i]]; if(e.cap>e.flow && d[x]==d[e.to]+1) { ok=1; p[e.to]=G[x][i]; cur[x]=i; x=e.to; break; } } if(!ok) { int m=n-1; for(unsigned i=0;i<G[x].size();i++) { Edge& e=edges[G[x][i]]; if(e.cap>e.flow) m=min(m,d[e.to]); } if(--num[d[x]]==0) break; num[d[x]=m+1]++; cur[x]=0; if(x!=s) x=edges[p[x]].from; } } return flow; } }; ISAP dinic; int n,m; inline int id_task(int x) {return x;} inline int id_time(int x) {return x+500;} int s = 0, t = 1001; void run() { scanf("%d%d",&n,&m); dinic.init(1001); int i,j; int a,b,c; int sum=0; for(i=1;i<=n;i++) { scanf("%d%d%d",&c,&a,&b); sum+=c; dinic.AddEdge(s,id_task(i),c); for(j=a;j<=b;j++) dinic.AddEdge(id_task(i),id_time(j),1); } for(i=1;i<=500;i++) dinic.AddEdge(id_time(i),t,m); // printf("%d ",dinic.Maxflow(0,500+500+1)); printf("Case %d: %s ",cas++,dinic.Maxflow(s,t)==sum?"Yes":"No"); } int main() { #ifdef LOCAL freopen("in","r",stdin); #endif int _; scanf("%d",&_); while(_--) run(); return 0; }
3. 78ms
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> #define FOR(i,n) for(i=0;i<=(n);i++) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int INF = 0xfffffff; const double eps = 1e-6; const int N = 1010; int cas = 1; const int maxn=1010; const int maxm=500010; struct edge{ int v,next,val; } G[maxm]; int s = 0, t = 1001; struct Dinic{ int pre[maxn],idx, sum; int N,M; int level[maxn]; int gap[maxn]; void add_edge(int from,int to,int val) { G[idx].v=to; G[idx].val=val; G[idx].next=pre[from]; pre[from]=idx++; G[idx].v=from; G[idx].val=0; G[idx].next=pre[to]; pre[to]=idx++; } int dfs(int pos,int cost, int cnt) { if (pos==t) { return cost; } int j,minh=cnt-1,lv=cost,d; for (j=pre[pos];j!=-1;j=G[j].next) { int v=G[j].v,val=G[j].val; if(val>0) { if (level[v]+1==level[pos]) { if (lv<G[j].val) d=lv; else d=G[j].val; d=dfs(v,d,cnt); G[j].val-=d; G[j^1].val+=d; lv-=d; if (level[s]>=cnt) return cost-lv; if (lv==0) break; } if (level[v]<minh) minh=level[v]; } } if (lv==cost) { --gap[level[pos]]; if (gap[level[pos]]==0) level[s]=cnt; level[pos]=minh+1; ++gap[level[pos]]; } return cost-lv; } int Maxflow(int s,int t, int cnt) { int flow=0; gap[s]=cnt; while (level[s]<cnt) { // int t=dfs(s,INF,cnt); flow+=dfs(s,INF, cnt); // flow+=t; // cout<<flow<<endl; } return flow; } void init() { memset(pre, -1, sizeof(pre)); memset(gap,0,sizeof(gap)); memset(level,0,sizeof(level)); sum = idx = 0; } }; Dinic dinic; int n,m; inline int id_task(int x) {return x;} inline int id_time(int x) {return x+500;} void run() { scanf("%d%d",&n,&m); dinic.init(); int i,j; int a,b,c; int sum=0; for(i=1;i<=n;i++) { scanf("%d%d%d",&c,&a,&b); sum+=c; dinic.add_edge(s,id_task(i),c); for(j=a;j<=b;j++) dinic.add_edge(id_task(i),id_time(j),1); } for(i=1;i<=500;i++) dinic.add_edge(id_time(i),t,m); // printf("%d ",dinic.Maxflow(0,500+500+1)); printf("Case %d: %s ",cas++,dinic.Maxflow(s,t,t+1)==sum?"Yes":"No"); } int main() { #ifdef LOCAL freopen("in","r",stdin); #endif int _; scanf("%d",&_); while(_--) run(); return 0; }
4.109ms
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> #define FOR(i,n) for(i=0;i<=(n);i++) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int INF = 1e9; const double eps = 1e-6; const int maxn = 1010; const int N = 1010; int cas = 1; const int inf = 0x3fffffff; template <int N, int M> struct Isap { int top; int d[N], pre[N], cur[N], gap[N]; struct Vertex{ int head; } V[N]; struct Edge{ int v, next; int c, f; } E[M]; void init(){ memset(V, -1, sizeof(V)); top = 0; } void add_edge(int u, int v, int c){ E[top].v = v; E[top].c = c; E[top].f = 0; E[top].next = V[u].head; V[u].head = top++; } void add(int u,int v, int c){ add_edge(u, v, c); add_edge(v, u, 0); } void set_d(int t){ queue<int> Q; memset(d, -1, sizeof(d)); memset(gap, 0, sizeof(gap)); d[t] = 0; Q.push(t); while(!Q.empty()) { int v = Q.front(); Q.pop(); ++gap[d[v]]; for(int i = V[v].head; ~i; i = E[i].next) { int u = E[i].v; if(d[u] == -1) { d[u] = d[v] + 1; Q.push(u); } } } } int sap(int s, int t, int num) { set_d(t); int ans = 0, u = s; int flow = inf; memcpy(cur, V, sizeof(V)); while(d[s] < num) { int &i = cur[u]; for(; ~i; i = E[i].next) { int v = E[i].v; if(E[i].c > E[i].f && d[u] == d[v] + 1) { u = v; pre[v] = i; flow = min(flow, E[i].c - E[i].f); if(u == t) { while(u != s) { int j = pre[u]; E[j].f += flow; E[j^1].f -= flow; u = E[j^1].v; } ans += flow; flow = inf; } break; } } if(i == -1) { if(--gap[d[u]] == 0) break; int dmin = num - 1; cur[u] = V[u].head; for(int j = V[u].head; ~j; j = E[j].next) if(E[j].c > E[j].f) dmin = min(dmin, d[E[j].v]); d[u] = dmin + 1; ++gap[d[u]]; if(u != s) u = E[pre[u] ^ 1].v; } } return ans; } }; Isap<1010, 1000000> Sap; //调用方式： //Sap.init(); //建边前调用 //Sap.add(u, v, c); //在u->v之间建一条容量为c的边 //Sap.sap(s, t, num); //s为源点，t为汇点，num为边的数量 int n,m; inline int id_task(int x) {return x;} inline int id_time(int x) {return x+500;} int s = 0, t = 1001; void run() { scanf("%d%d",&n,&m); Sap.init(); int i,j; int a,b,c; int sum=0; for(i=1;i<=n;i++) { scanf("%d%d%d",&c,&a,&b); sum+=c; Sap.add(s,id_task(i),c); for(j=a;j<=b;j++) Sap.add(id_task(i),id_time(j),1); } for(i=1;i<=500;i++) Sap.add(id_time(i),t,m); // printf("%d ",Sap.sap(s,t,t+100)); printf("Case %d: %s ",cas++,Sap.sap(s,t,t+1)==sum?"Yes":"No"); } int main() { #ifdef LOCAL freopen("in","r",stdin); #endif int _; scanf("%d",&_); while(_--) run(); return 0; }