【最大流】XMU 1595 机器调度

时间：2021-11-21 22:59:20

题目链接：

　　http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1595

题目大意：

　　T组数据，n个任务,m个机器,对于每个任务：有一个处理时间p(表示这个任务需要机器工作p天才能完成),一个释放时间r(表示该任务需要从第r天开始才能被处理),一个完成时间d(表示在第d天之前该任务必须完成)保证：d >= p + r。一个任务同一时间只能在一个机器上运行，但是运行时可以被中断，并移到另一个机器上运行。对于每台机器：在同一时间最多只能处理一个任务，在不同的时间可以处理不同的任务。问是否存在一个调度方案，使得所有任务均可以顺利完成？

题目思路：

　　【最大流】

　　没看出来是网络流问题。

　　将任务和该任务能运行的时间连边，S到任务连处理时间，时间到T连可运行机器数。

　　N个任务看成N个节点，对于每个时间夜也抽象成节点，然后设源和汇

　　源到任务节点连边，容量为该任务的时间，任务到每个可操作的时间节点连边，容量就是1，最后每个时间节点到汇点连边，容量为机器数量

　　最后求解最大流，若最大流=所有任务的总时间，则有解。

 
 //

 //by coolxxx

 //

 #include<iostream>

 #include<algorithm>

 #include<string>

 #include<iomanip>

 #include<memory.h>

 #include<time.h>

 #include<stdio.h>

 #include<stdlib.h>

 #include<string.h>

 #include<stdbool.h>

 #include<math.h>

 #define min(a,b) ((a)<(b)?(a):(b))

 #define max(a,b) ((a)>(b)?(a):(b))

 #define abs(a) ((a)>0?(a):(-(a)))

 #define lowbit(a) (a&(-a))

 #define sqr(a) ((a)*(a))

 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))

 #define eps 1e-8

 #define J 10

 #define MAX 0x7f7f7f7f

 #define PI 3.1415926535897

 #define inf 10000000

 #define N 504

 #define M 50004

 using namespace std;

 int n,m,lll,ans,cas;

 int nn,fl,s,t;

 int last[N],d[N],vd[N];

 struct xxx

 {

     int next,e,q;

 }a[M];

 void add(int x,int y,int z)

 {

     a[++lll].next=last[x];

     a[lll].e=y;

     a[lll].q=z;

     last[x]=lll;

 }

 int sap(int u,int f)

 {

     int i,v,tt,asp=,mix=nn-;

     if(u==t)return f;

     for(i=last[u];i!=;i=a[i].next)

     {

         v=a[i].e;

         if(a[i].q>)

         {

             if(d[u]==d[v]+)

             {

                 tt=sap(v,min(f-asp,a[i].q));

                 asp+=tt;

                 a[i].q-=tt;

                 a[i^].q+=tt;

                 if(asp==f || d[s]==nn)

                     return asp;

             }

             mix=min(mix,d[v]);

         }

     }

     if(asp!=)return asp;

     if(!--vd[d[u]])d[s]=nn;

     else vd[d[u]=mix+]++;

     return asp;

 }

 void build()

 {

     int i,j,x,y,z;

     s=++;t=++;

     nn=;

     for(i=;i<=n;i++)

     {

         scanf("%d%d%d",&x,&y,&z);

         fl+=x;nn=max(nn,z);

         add(s,i,x);add(i,s,);

         for(j=y;j<z;j++)

         {

             add(i,n+j,);add(n+j,i,);

         }

     }

     for(i=;i<=nn;i++)

     {

         add(n+i,t,m);add(t,n+i,);

     }

     nn+=n+;

     vd[]=nn;

 }

 int main()

 {

     #ifndef ONLINE_JUDGE

 //    freopen("1.txt","r",stdin);

 //    freopen("2.txt","w",stdout);

     #endif

     int i,j,k,l,f;

 //    while(~scanf("%s",s1))

 //    while(~scanf("%d",&n))

     for(scanf("%d",&cas),l=;l<=cas;l++)

     {

         fl=ans=;lll=;

         memset(d,,sizeof(d));

         memset(vd,,sizeof(vd));

         memset(last,,sizeof(last));

         scanf("%d%d",&n,&m);

         build();

         while(d[s]<nn)

         {

             f=sap(s,MAX);

             ans+=f;

         }

         if(ans==fl)puts("Yes");

         else puts("No");

     }

     return ;

 }

 /*

 //

 //

 */

相关文章