【CEOI2008】order

Source and Judge

CEOI2008
bzoj3709
luogu4177

Record

2h

Analysis

请先思考后再展开

决策问题考虑网络流
依赖关系再深入考虑到闭合子图
如果没用租用机器这个选项,这就是个裸题
租用机器和其他任务无关,考虑这个特征
如果x依赖y,将原本的INF改成租金,表示破除依赖关系

当前弧优化:
当层次确定的时候,反向弧是否使用也是确定的
那么如果一条边流完了,可以在边链表中去除
(有点类似欧拉路径的优化)
因为是层次图,不用担心dfs对第一个有效边数组的影响

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAX_N=2100;
int hou[MAX_N*2],cur[MAX_N*2];
struct Edge{int y,g,c;}e[MAX_N*MAX_N+2*MAX_N];
int ln;int oth(int x) {return x&1?x+1:x-1;}
void ins(int x,int y,int c)
{
e[++ln]=(Edge){y,hou[x],c};hou[x]=ln;
e[++ln]=(Edge){x,hou[y],0};hou[y]=ln;
}
int st,ed;
int h[MAX_N*2];
queue<int> q;
bool bfs()
{
memcpy(cur,hou,sizeof hou);
memset(h,0,sizeof h);
q.push(st);h[st]=1;
while(!q.empty())
{
int x=q.front();q.pop();
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;
if(h[y]==0 and e[k].c>0)
{
h[y]=h[x]+1;
q.push(y);
}
}
}
return h[ed]>0;
}
int dfs(int x,int now)
{
if(x==ed) return now;
int all=0;
for(int k=cur[x];k>0;k=e[k].g)
{
int y=e[k].y;
if(h[y]==h[x]+1 and e[k].c>0 and all<now)
{
int t=dfs(y,min(now-all,e[k].c));
all+=t;e[k].c-=t;e[oth(k)].c+=t;
}
if(e[k].c==0) cur[x]=e[k].g;
if(all==now) break;//剪枝1
}
if(all==0) h[x]=0;//剪枝2
return all;
}
void main()
{
int n,m;scanf("%d%d",&n,&m);
st=0;ed=n+m+1;
int ans=0;
for(int i=1;i<=n;i++)
{
int get;scanf("%d",&get);
ans+=get,ins(st,i,get);
int k;scanf("%d",&k);
while(k--)
{
int id,t;scanf("%d%d",&id,&t);
ins(i,n+id,t);
}
}
for(int i=1;i<=m;i++)
{
int t;scanf("%d",&t);
ins(n+i,ed,t);
}
while(bfs()) ans-=dfs(st,INF);
printf("%d",ans);
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/956c.html
转载请注明出处,谢谢!