Task Schedule

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4617 Accepted Submission(s): 1513


Problem Description Our geometry princess XMM has stoped her study in computational geometry to concentrate on her newly opened factory. Her factory has introduced M new machines in order to process the coming N tasks. For the i-th task, the factory has to start processing it at or after day Si, process it for Pi days, and finish the task before or at day Ei. A machine can only work on one task at a time, and each task can be processed by at most one machine at a time. However, a task can be interrupted and processed on different machines on different days.
Now she wonders whether he has a feasible schedule to finish all the tasks in time. She turns to you for help.

Input On the first line comes an integer T(T<=20), indicating the number of test cases.

You are given two integer N(N<=500) and M(M<=200) on the first line of each test case. Then on each of next N lines are three integers Pi, Si and Ei (1<=Pi, Si, Ei<=500), which have the meaning described in the description. It is guaranteed that in a feasible schedule every task that can be finished will be done before or at its end day.

Output For each test case, print “Case x: ” first, where x is the case number. If there exists a feasible schedule to finish all the tasks, print “Yes”, otherwise print “No”.

Print a blank line after each test case.

Sample Input

2
4 3
1 3 5 
1 1 4
2 3 7
3 5 9

2 2
2 1 3
1 2 2

Sample Output

Case 1: Yes
   
Case 2: Yes

最大流。這個題的建圖算是經典，因為限定每個時刻每台機器只能處理一個任務，所以可以把時間點分配給各個合法的機器...具體是先設定一個超級源點S，連向各個任務，容量為該任務所需時間，各個任務連向在范圍內的時間點，容量為1（保證每個時刻xxx這個條件），所有時間點連向超級匯點T，容量為機器台數，最後求最大流，等於所有機器所需時間和的就是yes 代碼：

#include 
#include 
#include 
#define SIZE 1100
#define INF 1000000000
using namespace std ;

struct Edge{
	int to , w , next ;
}edge[SIZE*SIZE];

int n , m , start , ends , index = 0;
int  head[SIZE] , level[SIZE] , cur[SIZE];
bool visited[SIZE] ;
bool bfs()
{
	queue que ;
	que.push(start) ;
	memset(level,-1,sizeof(level)) ;
	level[start] = 0 ;
	while(!que.empty())
	{
		int pos = que.front() ;
		que.pop() ;
		for(int next = head[pos] ; next != -1 ; next = edge[next].next)
		{
			if(level[edge[next].to]<0 && edge[next].w>0)
			{
				level[edge[next].to] = level[pos]+1 ;
				que.push(edge[next].to) ;
			}
		}
	}
	return level[ends] != -1 ;
}
int min(int a , int b)
{
	return a>b?b:a ;
}
int dfs(int pos , int flow)
{
	int deta = 0 , tmp = 0;
	if(pos == ends)
		return flow ;
	for(int next = head[pos] ; next != -1 ; next = edge[next].next)
	{
		if(edge[next].w > 0 && 
			level[pos] == level[edge[next].to]-1)
				{
					tmp = dfs(edge[next].to,min(flow-deta,edge[next].w)) ;
					if(tmp>0)
					{
						edge[next].w -= tmp ;
						edge[next^1].w += tmp ;
						deta += tmp ;
						if(deta == flow)
							break ;
					}
					else
						level[edge[next].to] = -1 ;		//不加這個，，超時。。。 
				}
	}
	return deta ;
}

int dinic()
{
	int ans = 0 , flow = 0 ;
	while(bfs())
	{
		int deta = 0 ;
		ans += dfs(0,INF) ;
	}
	return ans ;
}

void add(int s , int d , int w)
{
	edge[index].next = head[s] ;
	edge[index].to = d ;
	edge[index].w = w ;
	head[s] = index ++ ;
	
	edge[index].next = head[d] ;
	edge[index].to = s ;
	edge[index].w = 0 ;
	head[d] = index ++ ;
}

int main()
{
	int t , c = 1 ;
	scanf("%d",&t) ;
	while(t--)
	{
		scanf("%d%d",&n,&m) ;
		memset(head,-1,sizeof(head)) ;
		index = 0 ;
		int sum = 0 , max = -1;
		start = 0;
		for(int i = 1 ; i <= n ; ++i)
		{
			int x , y , z ;
			scanf("%d%d%d",&x,&y,&z) ;
			sum += x ;
			max = max>z?max:z ;
			add(start,i,x) ;
			for(int j = y ; j <= z ; ++j)
			{
				add(i,j+n,1) ;
			}
		}
		ends = n+max+1 ;
		for(int i = 1 ; i <= max ; ++i)
			add(i+n,ends,m) ;
		int ans = dinic() ;
		printf("Case %d: ",c++) ;
		if(ans != sum)
			puts("No\n") ;
		else
			puts("Yes\n");
	}
	return 0 ;
}

與君共勉