= =我承认我写网络流写疯了
= =我承认前面几篇博文都是扯淡，我写的是垃圾dinic（根本不叫dinic）
= =我承认这道题我调了半天
= =我承认我这道题一开始是T的，后来换上真正的dinic才过
= =我承认我还没理解dinic
= =我承认我一直到处改最后才发现输入顺序错了
= =我承认我已经疯了
= =我承认我写我承认上瘾了
回正题：这道题建图比较基础（但终于不是板题了），对于每个任务和每一天都建一个点（感觉把任务拆成若干点还能写二分图匹配），然后限制流量，然后判断是否满了
1 #include <cstdio> 2 #define INF 2147483647 3 int n,m,N,need,p,q,o,zl,h,t,T,tt,ans,fir[1005],nex[600000],to[600000],flo[600000],d[1005],l[1005]; 4 inline int min(int p,int q){ return(p<q)?p:q;} 5 inline void add(int p,int q,int o){ to[++N]=q;flo[N]=o;nex[N]=fir[p];fir[p]=N; 6 to[++N]=p;flo[N]=0;nex[N]=fir[q];fir[q]=N;} 7 int dfs(int now,int flow,int sum) 8 { 9 if(now==n+501) return flow; 10 for(int i=fir[now];i && (flow>sum);i=nex[i]) 11 if(d[to[i]]==d[now]+1 && flo[i]) 12 zl=dfs(to[i],min(flow,flo[i]),0),sum+=zl,flo[i]-=zl,flo[i^1]+=zl; 13 if(sum==0) d[now]=0; 14 return sum; 15 } 16 bool bfs() 17 { 18 for(int i=1;i<=n+501;i++) d[i]=0; 19 for(h=1,t=1,l[1]=0,d[0]=1;h<=t;h++) 20 for(int i=fir[l[h]];i;i=nex[i]) 21 if(!d[to[i]] && flo[i]) 22 l[++t]=to[i],d[l[t]]=d[l[h]]+1; 23 return d[n+501]; 24 } 25 int main() 26 { 27 for(scanf("%d",&T),tt=1;tt<=T;tt++) 28 { 29 scanf("%d%d",&n,&m);need=0;N=1; 30 for(int i=0;i<=n+501;i++) fir[i]=0; 31 for(int i=1;i<=n;i++) 32 { 33 scanf("%d%d%d",&o,&p,&q),add(0,i,o),need+=o; 34 for(int j=p;j<=q;j++) add(i,j+n,1); 35 } 36 for(int i=1;i<=500;i++) 37 add(i+n,n+501,m); 38 for(ans=0;bfs();ans+=dfs(0,INF,0)); 39 printf((ans==need)?"Case %d: Yes ":"Case %d: No ",tt); 40 } 41 return 0; 42 }