题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2883
思路：这道和hdu 3572很像http://www.cnblogs.com/wally/archive/2013/05/03/3056726.html。
这里也一样，我们选择0为源点，然后源点和顾客之间连边，容量为（ni*ti),然后，将每个顾客要求的时间区间看成点(由于区间可能覆盖），因此，我们可以直接对起始时间和结束时间进行排序，然后去掉重复的。这样假设我们排序后得到count个时间点，这样就有2*count-1个时间区间了，于是我们可以对每个时间区间与汇点连边，此时汇点为（vt=n+count+1),容量为m*(区间的差值），最后我们再判断顾客i的起始时间和结束时间si[i]~ei[i]这个区间包含某一个已经排好序的区间，如果包含，这顾客i与这个区间连边，容量为inf(以为顾客i满足这个要求）。如此建好图之后，SAP求一下最大流，如果sum(for all ni*ti)==maxflow,说明可以，否则，不能。
View Code
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 #define MAXM 444444 7 #define inf 1<<30 8 #define MAXN 2222 9 struct Edge{ 10 int v,cap,next; 11 }edge[MAXM]; 12 13 int pre[MAXN]; 14 int cur[MAXN]; 15 int head[MAXN]; 16 int level[MAXN]; 17 int gap[MAXN]; 18 int NV,NE; 19 int si[MAXN]; 20 int ei[MAXN]; 21 int time[MAXN]; 22 23 int SAP(int vs,int vt){ 24 memset(pre,-1,sizeof(pre)); 25 memset(level,0,sizeof(level)); 26 memset(gap,0,sizeof(gap)); 27 for(int i=0;i<=NV;i++)cur[i]=head[i]; 28 int u=pre[vs]=vs,maxflow=0,aug=-1; 29 gap[0]=NV; 30 while(level[vs]<NV){ 31 loop: 32 for(int &i=cur[u];i!=-1;i=edge[i].next){ 33 int v=edge[i].v; 34 if(edge[i].cap&&level[u]==level[v]+1){ 35 aug==-1?aug=edge[i].cap:(aug=min(aug,edge[i].cap)); 36 pre[v]=u; 37 u=v; 38 if(v==vt){ 39 maxflow+=aug; 40 for(u=pre[u];v!=vs;v=u,u=pre[u]){ 41 edge[cur[u]].cap-=aug; 42 edge[cur[u]^1].cap+=aug; 43 } 44 aug=-1; 45 } 46 goto loop; 47 } 48 } 49 int minlevel=vt; 50 for(int i=head[u];i!=-1;i=edge[i].next){ 51 int v=edge[i].v; 52 if(edge[i].cap&&minlevel>level[v]){ 53 cur[u]=i; 54 minlevel=level[v]; 55 } 56 } 57 gap[level[u]]--; 58 if(gap[level[u]]==0)break; 59 level[u]=minlevel+1; 60 gap[level[u]]++; 61 u=pre[u]; 62 } 63 return maxflow; 64 } 65 66 void Insert(int u,int v,int cap,int cc=0){ 67 edge[NE].v=v;edge[NE].cap=cap; 68 edge[NE].next=head[u];head[u]=NE++; 69 70 edge[NE].v=u;edge[NE].cap=cc; 71 edge[NE].next=head[v];head[v]=NE++; 72 } 73 74 int main(){ 75 int n,m,vs,vt,ni,ti,sum,total,count; 76 while(~scanf("%d%d",&n,&m)){ 77 NE=0,vs=0,sum=0,total=0,count=0; 78 memset(head,-1,sizeof(head)); 79 for(int i=1;i<=n;i++){ 80 scanf("%d%d%d%d",&si[i],&ni,&ei[i],&ti); 81 sum+=ni*ti; 82 Insert(vs,i,ni*ti); 83 time[total++]=si[i]; 84 time[total++]=ei[i]; 85 } 86 sort(time,time+total); 87 //去除重复空间 88 for(int i=1;i<total;i++){ 89 if(time[count]!=time[i]){time[++count]=time[i];} 90 } 91 vt=n+count+1; 92 NV=vt+1; 93 for(int i=1;i<=count;i++){ 94 Insert(n+i,vt,m*(time[i]-time[i-1]));//去重后的空间与vt连边 95 for(int j=1;j<=n;j++){ 96 //判断区间 97 if(si[j]<=time[i-1]&&ei[j]>=time[i]){ 98 Insert(j,i+n,inf);//符合就连边，且为inf; 99 } 100 } 101 } 102 if(sum==SAP(vs,vt)){ 103 puts("Yes"); 104 }else 105 puts("No"); 106 } 107 return 0; 108 }