HDU 3572 작업 스케줄 (최대 흐름 문제, sap 알고리즘)

5440 단어
/*
  : m   ,  n   ,       [si,ei]     ,  pi     。            ,
       m   。
  :         ,      ,         。
       ,  :              ,    s   t, s           ,     
  ;     t      ,   m;                ,   1。          。
  :sap  ,      Dinic  。
sap      :http://chuanwang66.iteye.com/blog/1450715
         ,         。
     :       ,       ,        。
*/


//sap      

#include <iostream>
using namespace std;
const int nMax = 2000;
const int mMax = 500000;
const int INF = 0x7fffffff;
struct Edge
{
	int v, w, next;
	Edge(){}
	Edge(int v, int w, int next):v(v), w(w), next(next){}
}adj[mMax];
int ind;
int head[nMax];//         
int dis[nMax];//       
int vn[nMax];//        
int t, n, m;
int pi, si, ei;
int source, sink, NV;//  、  、    

void addEdge(int u, int v, int w)
{
	adj[ind] = Edge(v, w, head[u]);
	head[u] = ind ++;
	adj[ind] = Edge(u, 0, head[v]);
	head[v] = ind ++;
}

int dfs(int cur, int cost)
{
	if(cur == sink)
		return cost;
	int leave = cost;//leave         
	int MinDis = NV;
	for(int id = head[cur]; id != -1; id = adj[id].next)
	{
		int v = adj[id].v;
		if(adj[id].w)
		{
			if(dis[v] + 1 == dis[cur])
			{
				int MinFlow = min(leave, adj[id].w);//      ,      leave adj[id].w  ,  leave       
				MinFlow = dfs(v, MinFlow);//   v   sink          
				adj[id].w -= MinFlow;
				adj[id ^ 1].w += MinFlow;
				leave -= MinFlow;
				if(dis[source] >= NV) return cost - leave;//    -     
				if(leave == 0) break;
			}
			if(dis[v] < MinDis)//MinDis   cur          ,              。
				MinDis = dis[v];
		}
	}
	if(leave == cost)//         ,         
	{
		if((-- vn[dis[cur]]) == 0) dis[source] = NV;
		dis[cur] = MinDis + 1;
		vn[dis[cur]] ++;
	}
	return cost - leave;
}

int sap(int s, int e)
{
	source = s;
	sink = e;
	NV = e + 1;
	memset(dis, 0, sizeof(dis));
	memset(vn, 0, sizeof(vn));
	vn[0] = NV;
	int ans = 0;
	while(dis[source] < NV)//  dis[source] >= NV      
	{
		ans += dfs(s,INF);
	}
	return ans;
}

int main()
{
	//freopen("e://data.in", "r", stdin);
	int s, e;
	scanf("%d", &t);
	for(int cas = 1; cas <= t; cas ++)
	{
		int Max = 0;
		int sum = 0;
		s = 0;
		ind = 0;
		memset(head, -1, sizeof(head));
		scanf("%d %d", &n, &m);
		for(int i = 1; i <= n; ++ i)
		{
			scanf("%d %d %d", &pi, &si, &ei);
			sum += pi;
			addEdge(s, i, pi);
			Max = max(Max, ei);
			for(int j = si; j <= ei; ++ j)
				addEdge(i, n + j, 1);
		}
		e = n + Max + 1;
		for(int i = 1; i <= Max; ++ i)
			addEdge(n + i, e, m);
		int a;
		if((a = sap(s, e)) == sum)
			printf("Case %d: Yes

", cas); else printf("Case %d: No

", cas); } return 0; } // #include <iostream> //#define TEST using namespace std; const int nMax = 2000; const int mMax = 500000; const int INF = 0x7fffffff; struct Edge { int u, v, w; int next; Edge(){} Edge(int u, int v, int w, int next):u(u), v(v), w(w), next(next){} }adj[mMax]; int ind; int dis[nMax];// int pre[nMax];// int head[nMax];// int flow[nMax];// int vn[nMax];// int cur[nMax];// int t, n, m; int pi, si, ei; void addEdge(int u, int v, int w)// { adj[ind] = Edge(u, v, w, head[u]); head[u] = ind ++; adj[ind] = Edge(v, u, 0, head[v]); head[v] = ind ++; } int sap(int s, int e, int n)//sap , { int u = s; int MaxFlow = 0; memset(dis, 0, sizeof(dis)); flow[s] = INF; memset(vn, 0, sizeof(vn)); pre[s] = -1; for(int i = 0; i < n; ++ i) cur[i] = head[i];// while(d[s] < n)// d[s] < n, , while(1) { bool flag = false; if(u == e) { MaxFlow += flow[e]; for(int v = pre[e]; v != -1; v = pre[v]) { int id = cur[v]; adj[id].w -= flow[e];// adj[id ^ 1].w += flow[e]; if(adj[id].w == 0) u = v;// 0 , 0, } } for(int id = cur[u]; id != -1; id = adj[id].next)// { int v = adj[id].v; if(adj[id].w > 0 && dis[v] + 1 == dis[u]) { flag = true; pre[v] = u; flow[v] = min(flow[u], adj[id].w); cur[u] = id; u = v; break; } } if(!flag)// , dis[u] { if((-- vn[dis[u]]) == 0) break;// int MinDis = n;// , dis[v] cur[u] = head[u]; for(int id = head[u]; id != -1; id = adj[id].next) { int v = adj[id].v; if(adj[id].w > 0 && dis[v] < MinDis)//edge[i].w > 0 , { MinDis = dis[v]; cur[u] = id; } } dis[u] = MinDis + 1;// dis[u] vn[dis[u]] ++; if(u != s) u = pre[u];// } } return MaxFlow; } int main() { //freopen("e://data.in", "r", stdin); //freopen("e://data2.out", "w", stdout); int s, e; scanf("%d", &t); for(int cas = 1; cas <= t; cas ++) { int Max = 0; int sum = 0; s = 0; ind = 0; memset(head, -1, sizeof(head)); scanf("%d %d", &n, &m); for(int i = 1; i <= n; ++ i) { scanf("%d %d %d", &pi, &si, &ei); sum += pi; addEdge(0, i, pi); Max = max(Max, ei); for(int j = si; j <= ei; ++ j) addEdge(i, n + j, 1); } e = n + Max + 1; for(int i = 1; i <= Max; ++ i) addEdge(n + i, e, m); if(sap(s, e, e + 1) == sum) printf("Case %d: Yes

", cas); else printf("Case %d: No

", cas); } return 0; }

좋은 웹페이지 즐겨찾기