。。。建图。判满流。
建图方式:
源点到机器连边。容量为最大值。
机器到第i天连边,容量为1
第i天到事件连边,容量为1
所有事件到汇点连边。容量为所需时间。
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <set> #include <vector> #include <map> #include <queue> #include <set> #include <algorithm> #include <limits.h> using namespace std; #define MAXN 1500 #define MAXM 600000 const int INF = INT_MAX; typedef long long LL; struct Edge { int from,to,ci,next; Edge(){} Edge(int _from,int _to,int _ci,int _next):from(_from),to(_to),ci(_ci),next(_next){} }e[MAXM]; int head[MAXN],tot; int dis[MAXN]; int top,sta[MAXN],cur[MAXN]; int n,m; inline void init(){ memset(head,-1,sizeof(head)); tot=0; } inline void AddEdge(int u,int v,int ci0,int ci1=0){ e[tot]=Edge(u,v,ci0,head[u]); head[u]=tot++; e[tot]=Edge(v,u,ci1,head[v]); head[v]=tot++; } inline bool bfs(int st,int et){ memset(dis,0,sizeof(dis)); dis[st]=1; queue <int> q; q.push(st); while(!q.empty()){ int now=q.front(); q.pop(); for(int i=head[now];i!=-1;i=e[i].next){ int next=e[i].to; if(e[i].ci&&!dis[next]){ dis[next]=dis[now]+1; if(next==et)return true; q.push(next); } } } return false; } LL Dinic(int st,int et){ LL ans=0; while(bfs(st,et)){ //printf("here\n"); top=0; memcpy(cur,head,sizeof(head)); int u=st,i; while(1){ if(u==et){ int pos,minn=INF; //printf("top:%d\n",top); for(i=0;i<top;i++) { if(minn>e[sta[i]].ci){ minn=e[sta[i]].ci; pos=i; } //printf("%d --> %d\n",e[sta[i]].from,e[sta[i]].to); } for(i=0;i<top;i++){ e[sta[i]].ci-=minn; e[sta[i]^1].ci+=minn; } top=pos; u=e[sta[top]].from; ans+=minn; //printf("minn:%d\n\n",minn); } for(i=cur[u];i!=-1;cur[u]=i=e[i].next) if(e[i].ci&&dis[u]+1==dis[e[i].to])break; if(cur[u]!=-1){ sta[top++]=cur[u]; u=e[cur[u]].to; } else { if(top==0)break; dis[u]=0; u=e[sta[--top]].from; } } } return ans; } struct point { int pi,si,ei; }cs[MAXN]; int main() { int t,cas=0; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); int day=500; init(); //printf("%d %d\n",n,m); int tt=0; for(int i=1;i<=n;i++) { scanf("%d%d%d",&cs[i].pi,&cs[i].si,&cs[i].ei); tt+=cs[i].pi; //if(cs[i].ei>day)day=cs[i].ei; } //printf("here\n"); //源点 -->0 //1~m -->机器 for(int i=0;i<m;i++) { AddEdge(0,i+1,day); } //m+1~m+day -->第几天 for(int i=1;i<=m;i++) { for(int j=1;j<=day;j++) AddEdge(i,j+m,1); } //m+day+1~m+day+n -->事件 for(int i=1;i<=day;i++) for(int j=1;j<=n;j++) { if(cs[j].si<=i&&i<=cs[j].ei) AddEdge(i+m,m+day+j,1); } //汇点 -->m+day+n+1 for(int i=1;i<=n;i++) AddEdge(i+m+day,m+day+n+1,cs[i].pi); //printf("pi:%d\n",tt); //printf("%I64d\n",Dinic(0,m+day+n+1)); printf("Case %d: ",++cas); if(tt==Dinic(0,m+day+n+1))puts("Yes\n"); else puts("No\n"); } return 0; }