HDU 3572 작업 스케줄 (최대 흐름 문제, sap 알고리즘)
/*
: 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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.