YY了好久才弄出来。。。。每次问题都被喷。。。好伤心。。。
#include<stdio.h>#include<string.h>#include<queue>#include<algorithm>using namespace std;#define N 1005#define INF 0x7ffffffint n,m,k;int level[N];struct node{int to,next,cost;}edge[N*N];int head[N];int t_head[N];int start,end;void init(){k=0;memset(head,-1,sizeof(head));}int bfs(int s,int t)//对顶点进行标号、找出层次图{memset(level,0,sizeof(level));queue<int>q;q.push(s);level[s]=1;while(!q.empty()){int now=q.front();q.pop();for(int i=head[now];i!=-1;i=edge[i].next){int y=edge[i].to;if(!level[y]&&edge[i].cost>0){level[y]=level[now]+1;q.push(y);}}}return level[t]!=0;//汇点是否在层次图中}int dfs(int s,int cp)//在层次图中寻找增广路进行增广{int flow=0,temp;int t;if(s==end||cp==0)return cp;for(;t_head[s]+1;t_head[s]=edge[t_head[s]].next){int y=edge[t_head[s]].to;if(level[s]+1==level[y]){temp=dfs(y,min(cp,edge[t_head[s]].cost));if(temp>0){edge[t_head[s]].cost-=temp;edge[t_head[s]^1].cost+=temp;flow+=temp;cp-=temp;if(cp==0)break;}}}return flow;}int dinic(){int ans=0,flow=0;while(bfs(start,end))//汇点不在层次图中、算法终止{for(int i=0;i<=end;i++)t_head[i]=head[i];ans+=dfs(start,INF);}return ans;}void add(int x,int y,int val){edge[k].to=y;edge[k].cost=val;edge[k].next=head[x];head[x]=k++;edge[k].to=x;edge[k].cost=0;edge[k].next=head[y];head[y]=k++;}int main(){int t;int cas=1;scanf("%d",&t);while(t–){scanf("%d%d",&n,&m);init();int sum=0;start=0,end=500+n+1;for(int i=1;i<=n;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);sum+=x;add(start,i,x);for(int j=y;j<=z;j++)add(i,j+n,1);}for(int i=1;i<=500;i++)add(i+n,end,m);int ans=dinic();printf("Case %d: ",cas++);if(ans!=sum)printf("No\n\n");else printf("Yes\n\n");}return 0;}
，与其在那里苦苦挣扎，碍于面子硬撑，倒不如微笑着面对，
