题目链接：传送门
题目大意：有n个任务，m个机器。每个机器最早在 Si 天开始，最晚在 Ei 天结束，需要 Pi 天完成。可以中途换机器做，也可以中途打断不做，过后再做
只要在规定时间内都行。每个机器一天只能处理一个任务。问是否能在规定时间完成。
题目思路：知道是网络流，但是不会建图。
自己建图的时候，想法是 S 与任务建边容量为Pi，然后 T 与机器建边，容量为inf，然后时间就不知道怎么处理了。 卡死在这了。
其实知道 任务，机器，时间这三个条件后完全可以变通一下建图的，但是没有转过弯来。还需要继续努力。
正解： 让 S 与任务连边，容量为Pi，T 与时间连边，容量为机器数，任务和时间连边（从起始时间到结束时间），容量 1。
这样把所有限制条件都利用了起来，最后只需判断 最大流与 sum(Pi) 是否相等。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <cstring> #include <stack> #include <cctype> #include <queue> #include <string> #include <vector> #include <set> #include <map> #include <climits> #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define fi first #define se second #define ping(x,y) ((x-y)*(x-y)) #define mst(x,y) memset(x,y,sizeof(x)) #define mcp(x,y) memcpy(x,y,sizeof(y)) using namespace std; #define gamma 0.5772156649015328606065120 #define MOD 1000000007 #define inf 0x3f3f3f3f #define N 1105 #define maxn 500005 typedef pair<int,int> PII; typedef long long LL; int head[N],cur[N],pre[N],d[N],gap[N]; int n,m,hcnt,S,T,sum; struct Node{ int to,nxt,v; Node(){} Node(int a,int b,int c):to(a),nxt(b),v(c){} }node[maxn]; inline void add(int x,int y,int v){ node[hcnt]=Node(y,head[x],v);head[x]=hcnt++; node[hcnt]=Node(x,head[y],0);head[y]=hcnt++; } bool ISAP(int S,int T,int n){ ///起点,终点,总共点数(加上源汇点) int ans=0,aug=inf,i,flag; ///最大流,可增广流量,.,标记 int u,e,dis; ///当前点,当前可达点 mst(gap,0);mst(d,0); for(i=0;i<=n;++i) cur[i]=head[i]; u=pre[S]=S; while(d[S]<n){ flag=0; for(i=cur[u];~i;i=node[i].nxt){ e=node[i].to; if(node[i].v>0&&d[u]==d[e]+1){ flag=1; break; } } if(flag){ pre[e]=u; cur[u]=i; aug=min(aug,node[i].v); u=e; if(u==T){ while(u!=S){ u=pre[u]; node[cur[u]].v-=aug; node[cur[u]^1].v+=aug; } u=S; ans+=aug; aug=inf; } } else{ if(--gap[d[u]]==0)break; dis=n; cur[u]=head[u]; for(int i=head[u];~i;i=node[i].nxt){ e=node[i].to; if(node[i].v>0&&d[e]+1<dis){ dis=d[e]+1; cur[u]=i; } } d[u]=dis; ++gap[dis]; if(u!=S) u=pre[u]; } } return ans==sum; } int main(){ int i,j,group,x,y,v; scanf("%d",&group); for(int g=1;g<=group;++g){ mst(head,-1);hcnt=0; scanf("%d%d",&n,&m); sum=S=0;T=n+500+1; for(i=1;i<=n;++i){ scanf("%d%d%d",&v,&x,&y); sum+=v; add(S,i,v); for(j=x;j<=y;++j) add(i,n+j,1); } for(i=1;i<=500;++i)add(i+n,T,m); printf("Case %d: ",g); if(ISAP(S,T,T+1))printf("Yes "); else printf("No "); } return 0; }