| Solved | A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|---|
| 7/7 | O | O | Ø | O | O | Ø | Ø |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A CF1082G - Petya and Graph
题目描述
给一个无向图，其中每个边和点都分别有正的边权和点权，定义一个子图的价值为所有边的权值之和减去所有点的权值之和，要求所有边的两个顶点都在该子图中。求这个无向图最大的子图价值。
解题思路
最大权闭合子图。
构图：（设边对应点为$w$，点对应点为$u,v$）
$S\rightarrow w\rightarrow u,v\rightarrow T$
边权$w_i,inf,a_u(a_v)$
求最小割，割完后与$S$相连的就是答案对应的子图。答案即为所有边的权值减去最小割。
AC代码
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
typedef long long ll;
using namespace std;
struct Edge{
ll l;
int e,n;
}e[N<<1];
int hd[N],cur[N],cnt=1;
void add(int a,int b,ll l){
e[++cnt].e=b;e[cnt].l=l;e[cnt].n=hd[a];hd[a]=cnt;
e[++cnt].e=a;e[cnt].l=0;e[cnt].n=hd[b];hd[b]=cnt;
}
ll inf=1e15;
int n,m,s,t;
ll a[N];
int dep[N];
queue<int>Q;
ll dfs(int p,ll flow){
if(p==t)return flow;
int i;
for(i=cur[p];i;i=e[i].n){
int q=e[i].e;
cur[p]=i;
if(dep[q]==1+dep[p]&&e[i].l){
ll ans=dfs(q,min(flow,e[i].l));
if(ans){
e[i].l-=ans;
e[i^1].l+=ans;
return ans;
}
}
}
return 0;
}
int bfs(){
memset(dep,0,sizeof(dep));
Q.push(s);dep[s]=1;
int i;
while(!Q.empty()){
int p=Q.front();Q.pop();
for(i=hd[p];i;i=e[i].n){
int q=e[i].e;
if(!dep[q]&&e[i].l)dep[q]=dep[p]+1,Q.push(q);
}
}
return dep[t];
}
ll dinic(){
int i;
ll d,ans=0;
while(bfs()){
for(i=0;i<=t;i++)cur[i]=hd[i];
while((d=dfs(s,inf)))ans+=d;
}
return ans;
}
int main(){
int i,u,v;
ll w,sum=0;
scanf("%d%d",&n,&m);
s=0;t=n+m+1;
for(i=1;i<=n;i++)scanf("%I64d",&a[i]),add(i+m,t,a[i]);
for(i=1;i<=m;i++){
scanf("%d%d%I64d",&u,&v,&w);
add(s,i,w);
add(i,u+m,inf);
add(i,v+m,inf);
sum+=w;
}
printf("%I64d",sum-dinic());
return 0;
}
B CF513F2 - Scaygerboss
题目描述
有一个带障碍的地图，有$male $个男性$scayger$，$female$个女性$scayger$，一个$other$性别$scaygerboss$，分别有其初始坐标和走一个格子需要花费的时间。定义一个$scayger$高兴当且仅当它和与它不同性别的另一个$scayger$占有一个格子，且这个格子只有他们两个。问最少要多长时间所有的$scayger$都高兴。
解题思路
先暴力判断$boss$充当的性别，然后二分答案、$bfs$建边即可。
构图：（流量均为$1$）
$S\rightarrow male\rightarrow male在t内能去的地方\rightarrow 这个格子的拆点\rightarrow 能在t内去这个格子的female\rightarrow T$
AC代码
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
typedef long long ll;
using namespace std;
struct Edge{
ll l;
int e,n;
}e[N*N*N*N*N];
int hd[N*N*5],cur[N*N*5],cnt=1;
void add(int a,int b,ll l){
e[++cnt].e=b;e[cnt].l=l;e[cnt].n=hd[a];hd[a]=cnt;
e[++cnt].e=a;e[cnt].l=0;e[cnt].n=hd[b];hd[b]=cnt;
}
ll inf=1e15;
int n,m,s,t;
int dep[N*N*5];
queue<int>Q;
ll dfs(int p,ll flow){
if(p==t)return flow;
int i;
for(i=cur[p];i;i=e[i].n){
int q=e[i].e;
cur[p]=i;
if(dep[q]>dep[p]&&e[i].l){
ll ans=dfs(q,min(flow,e[i].l));
if(ans){
e[i].l-=ans;
e[i^1].l+=ans;
return ans;
}
}
}
return 0;
}
int bfs(){
memset(dep,0,sizeof(dep));
Q.push(s);dep[s]=1;
int i;
while(!Q.empty()){
int p=Q.front();Q.pop();
for(i=hd[p];i;i=e[i].n){
int q=e[i].e;
if(!dep[q]&&e[i].l)dep[q]=dep[p]+1,Q.push(q);
}
}
return dep[t];
}
ll dinic(){
int i;
ll d,ans=0;
while(bfs()){
for(i=0;i<=t;i++)cur[i]=hd[i];
while((d=dfs(s,inf)))ans+=d;
}
return ans;
}
char a[N][N];
int sign[N][N];
struct Per{
int x,y;
ll v;
}boy[N*N],gir[N*N];
int boyn,girn;
struct QUEUE{
int x,y;
ll time;
};
int vis[N][N];
int num;//'.'
int in(int flag,int NUM,int x,int y){
if(x>=0&&y>=0&&x<n&&y<m&&!vis[x][y]&&a[x][y]=='.'){
vis[x][y]=1;
if(flag)add(NUM,sign[x][y]+boyn+girn,1);//male
else add(sign[x][y]+boyn+girn+num,NUM,1);//female
return 1;
}
return 0;
}
int jud(ll tim){
int i,j;
int now=0;
memset(hd,0,sizeof(hd));cnt=1;
for(i=0;i<n;i++)for(j=0;j<m;j++)if(a[i][j]=='.'){
sign[i][j]=++now;
add(boyn+girn+now,boyn+girn+num+now,1);
}
for(i=0;i<boyn;i++)add(s,i+1,1);
for(i=0;i<girn;i++)add(i+1+boyn,t,1);
for(i=0;i<boyn;i++){//bfs
int p=i+1;
memset(vis,0,sizeof(vis));
queue<QUEUE>Q;
while(!Q.empty())Q.pop();
in(1,p,boy[i].x-1,boy[i].y-1);
Q.push({boy[i].x-1,boy[i].y-1,0});
while(!Q.empty()){
int x=Q.front().x,y=Q.front().y;ll t=Q.front().time;Q.pop();
if(t+boy[i].v>tim)break;
if(in(1,p,x+1,y))Q.push({x+1,y,t+boy[i].v});
if(in(1,p,x-1,y))Q.push({x-1,y,t+boy[i].v});
if(in(1,p,x,y+1))Q.push({x,y+1,t+boy[i].v});
if(in(1,p,x,y-1))Q.push({x,y-1,t+boy[i].v});
}
}
for(i=0;i<girn;i++){//bfs
int p=i+1+boyn;
memset(vis,0,sizeof(vis));
queue<QUEUE>Q;
while(!Q.empty())Q.pop();
in(0,p,gir[i].x-1,gir[i].y-1);
Q.push({gir[i].x-1,gir[i].y-1,0});
while(!Q.empty()){
int x=Q.front().x,y=Q.front().y;ll t=Q.front().time;Q.pop();
if(t+gir[i].v>tim)break;
if(in(0,p,x+1,y))Q.push({x+1,y,t+gir[i].v});
if(in(0,p,x-1,y))Q.push({x-1,y,t+gir[i].v});
if(in(0,p,x,y+1))Q.push({x,y+1,t+gir[i].v});
if(in(0,p,x,y-1))Q.push({x,y-1,t+gir[i].v});
}
}
return dinic()==(boyn+girn)/2;
}
int main(){
int i,j,girnum=0,boynum=0;
scanf("%d%d%d%d",&n,&m,&boyn,&girn);
for(i=0;i<n;i++){
scanf("%s",a[i]);
for(j=0;j<m;j++)if(a[i][j]=='.')num++;
}
if(num<(boyn+girn+1)/2||(boyn-girn!=1&&girn-boyn!=1))return printf("-1"),0;
ll l=0,r=490e9,ans=1e18;
if(boyn-girn==1)scanf("%d%d%I64d",&gir[girnum].x,&gir[girnum].y,&gir[girnum].v),girnum++,girn++;
else scanf("%d%d%I64d",&boy[boynum].x,&boy[boynum].y,&boy[boynum].v),boynum++,boyn++;
while(boynum<boyn)scanf("%d%d%I64d",&boy[boynum].x,&boy[boynum].y,&boy[boynum].v),boynum++;
while(girnum<girn)scanf("%d%d%I64d",&gir[girnum].x,&gir[girnum].y,&gir[girnum].v),girnum++;
s=0;t=boyn+girn+num*2+2;
while(l<=r){
ll mid=(l+r)>>1;
if(jud(mid))ans=mid,r=mid-1;
else l=mid+1;
}
printf("%I64d",ans<1e18?ans:-1);
return 0;
}
C CF1045A - Last chance
题目描述
有$m$个敌人，$n$次攻击，每次攻击可以选择以下三种之一：
- 攻击给定集合里至多一个敌人
- 攻击给定区间里至多一个敌人
- 攻击给定三人中的两人或零人
其中保证所有敌人至多会位于攻击方式$3$的集合一次。
每个敌人都是一击即死，所以每个敌人只能打一次。
问最多能打死几个敌人，并输出这些敌人分别是被哪回合的攻击打死的。
解题思路
攻击$1$直接暴力连边，攻击$2$线段树优化建图连边即可。而攻击$3$可以暴力打死其中两人$BC$，并连$p\rightarrow a$，$b\rightarrow p$，$c\rightarrow p$三条边，不连$s\rightarrow p$边即可（$p$指本次攻击对应的点）。
难点在于最后的输出。可以考虑连一个反向的图，沿着流方向回流到攻击所对应点。
AC代码
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
typedef long long ll;
using namespace std;
struct Edge{
ll l;
int e,n;
}e[N<<1];
int hd[N],cur[N],cnt=1;
void add(int a,int b,ll l){
e[++cnt].e=b;e[cnt].l=l;e[cnt].n=hd[a];hd[a]=cnt;
e[++cnt].e=a;e[cnt].l=0;e[cnt].n=hd[b];hd[b]=cnt;
}
ll inf=1e15;
int n,m,s,t;
ll a[N];
int dep[N];
queue<int>Q;
ll dfs(int p,ll flow){
if(p==t)return flow;
int i;
for(i=cur[p];i;i=e[i].n){
int q=e[i].e;
cur[p]=i;
if(dep[q]==dep[p]+1&&e[i].l){
ll ans=dfs(q,min(flow,e[i].l));
if(ans){
e[i].l-=ans;
e[i^1].l+=ans;
return ans;
}
}
}
return 0;
}
int bfs(){
memset(dep,0,sizeof(dep));
Q.push(s);dep[s]=1;
int i;
while(!Q.empty()){
int p=Q.front();Q.pop();
for(i=hd[p];i;i=e[i].n){
int q=e[i].e;
if(!dep[q]&&e[i].l)dep[q]=dep[p]+1,Q.push(q);
}
}
return dep[t];
}
int tot;//节点
ll dinic(){
int i;
ll d,ans=0;
while(bfs()){
for(i=0;i<=tot;i++)cur[i]=hd[i];
while((d=dfs(s,inf)))ans+=d;
}
return ans;
}
int id[N],L[N],R[N];
void build(int p,int l,int r){
id[p]=++tot;
L[p]=l;R[p]=r;
if(l==r){
add(tot,l,1);
return;
}
build(p<<1,l,(l+r)>>1);
build(p<<1|1,((l+r)>>1)+1,r);
add(id[p],id[p<<1],inf);
add(id[p],id[p<<1|1],inf);
}
void upd(int p,int l,int r){
if(L[p]>=l&&R[p]<=r){
add(tot,id[p],1);
return;
}
if(L[p]>r||R[p]<l)return;
upd(p<<1,l,r);
upd(p<<1|1,l,r);
}
map<int,int>mp[N];
int vis[N],start,ret;
void solve(int x){
if(x>=start){ret=x-start;return;}
map<int,int>::iterator it=mp[x].begin();
solve(it->first);
--it->second;
if(!it->second)mp[x].erase(it);
}
int main(){
int i,j,u,k,l,r,opt;
int temp=0;
scanf("%d%d",&n,&m);
tot=m;
build(1,1,m);
s=++tot;t=++tot;
start=tot;
for(i=1;i<=n;i++){
++tot;
scanf("%d",&opt);
if(opt==0){
add(s,tot,1);
scanf("%d",&k);
while(k--)scanf("%d",&u),add(tot,u,1);
}else if(opt==1){
add(s,tot,1);
scanf("%d%d",&l,&r);
upd(1,l,r);
}else{
int A,B,C;
scanf("%d%d%d",&A,&B,&C);
add(tot,A,1);
add(tot,B,0);e[cnt].l=1;vis[B]=1;
add(tot,C,1);e[cnt].l=1;vis[C]=1;
temp+=2;
}
}
for(i=1;i<=m;i++)if(!vis[i])add(i,t,1);
printf("%I64d\n",dinic()+temp);
for(i=1;i<=tot;i++)
for(j=hd[i];j;j=e[j].n)
if((j&1)&&e[j].l)mp[i][e[j].e]=e[j].l;
for(i=1;i<=m;i++){
int flag=0;
for(j=hd[i];j;j=e[j].n)if(e[j].e==t&&e[j].l){
flag=1;
break;
}
if(flag)continue;
solve(i);
printf("%d %d\n",ret,i);
}
return 0;
}
D CF164C - Machine Programming
题目描述
有一堆任务，$k$个机器，每个任务有起始结束时间以及利润，问如何分配能够利益最大化。
解题思路
先把任务按照起始时间排序，把每个任务拆点，连边如下
$S\rightarrow i$，流量$k$，费用$0$
$i\rightarrow i+1$，流量$inf$，费用$0$
$i’\rightarrow t$，流量$inf$，费用$0$
$i$完成后首先开始的$j$：$i’\rightarrow j$，流量$1$，费用$0$
$i\rightarrow i’$，流量$1$，费用$-profit$跑最小费用最大流，保证使用最多的机器的情况下获得利润负值最小。
AC代码
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
using namespace std;
struct Edge{
int end,len,cost,near;
}e[20*N];
struct Pre{
int pre,edge;
}pre[N];
int head[N],dis[N],flow[N],vis[N],cnt=1,n,k,s,t;
int maxflow,mincost;
int inf=2e9;
void add(int a,int b,int l,int c){
e[++cnt].end=b;
e[cnt].len=l;
e[cnt].cost=c;
e[cnt].near=head[a];
head[a]=cnt;
}
queue<int>Q;
int spfa(){
memset(dis,0x7f,sizeof(dis));
memset(flow,0x7f,sizeof(flow));
memset(vis,0,sizeof(vis));
while(!Q.empty())Q.pop();
int i,top,q;
Q.push(s);vis[s]=1;dis[s]=0;pre[t].pre=0;
while(!Q.empty()){
top=Q.front();
Q.pop();
vis[top]=0;
for(i=head[top];i;i=e[i].near){
q=e[i].end;
if(e[i].len&&dis[q]>dis[top]+e[i].cost){
dis[q]=dis[top]+e[i].cost;
pre[q].pre=top;
pre[q].edge=i;
flow[q]=min(flow[top],e[i].len);
if(!vis[q]){
vis[q]=1;
Q.push(q);
}
}
}
}
return pre[t].pre;
}
void ek(){
int i;
while(spfa()){
maxflow+=flow[t];
mincost+=flow[t]*dis[t];
for(i=t;i!=s;i=pre[i].pre){
e[pre[i].edge].len-=flow[t];
e[pre[i].edge^1].len+=flow[t];
}
}
}
struct A{
int s,t,c,i;
bool operator<(const A&p)const{return s<p.s||(s==p.s&&t<p.t);}
}a[N];
int ans[N];
int main(){
int i,j;
scanf("%d%d",&n,&k);
for(i=0;i<n;i++)scanf("%d%d%d",&a[i].s,&a[i].t,&a[i].c),a[i].i=i;
sort(a,a+n);
s=2*n;t=s+1;
add(s,0,k,0);add(0,s,0,0);
add(n-1,t,k,0);add(t,n-1,0,0);
for(i=0;i<n;i++){
add(i,i+n,1,-a[i].c),add(i+n,i,0,a[i].c);
add(i+n,t,inf,0),add(t,i+n,0,0);
int j=i+1;
while(j<n&&a[j].s<a[i].s+a[i].t)j++;
if(j<n)add(i+n,j,inf,0),add(j,i+n,0,0);
if(i<n-1)add(i,i+1,inf,0),add(i+1,i,0,0);
}
ek();
for(i=0;i<n;i++){
for(j=head[i];j;j=e[j].near){
int q=e[j].end;
if(q==i+n){
if(!e[j].len)ans[a[i].i]=1;
break;
}
}
}
for(i=0;i<n;i++)printf("%d ",ans[i]);
return 0;
}
E POJ 1273 - Drainage Ditches
题目描述
求最大流。
解题思路
模板。
必须吐槽$poj$居然不能用万能头！
AC代码
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
typedef long long ll;
using namespace std;
struct Edge{
int l,e,n;
}e[M<<1];
int hd[M],cur[M],cnt=1;
void add(int a,int b,int l){
e[++cnt].e=b;e[cnt].l=l;e[cnt].n=hd[a];hd[a]=cnt;
e[++cnt].e=a;e[cnt].l=0;e[cnt].n=hd[b];hd[b]=cnt;
}
int inf=1e9;
int n,m,s,t;
ll sum;
int dep[M];
queue<int>Q;
int dfs(int p,int flow){
if(p==t)return flow;
int i;
for(i=cur[p];i;i=e[i].n){
int q=e[i].e;
cur[p]=i;
if(dep[q]>dep[p]&&e[i].l){
int ans=dfs(q,min(flow,e[i].l));
if(ans){
e[i].l-=ans;
e[i^1].l+=ans;
return ans;
}
}
}
return 0;
}
int bfs(){
memset(dep,0,sizeof(dep));
Q.push(s);dep[s]=1;
int i;
while(!Q.empty()){
int p=Q.front();Q.pop();
for(i=hd[p];i;i=e[i].n){
int q=e[i].e;
if(!dep[q]&&e[i].l)dep[q]=dep[p]+1,Q.push(q);
}
}
return dep[t];
}
ll dinic(){
int i,d;
ll ans=0;
while(bfs()){
for(i=0;i<=t;i++)cur[i]=hd[i];
while((d=dfs(s,inf)))ans+=d;
}
return ans;
}
int main(){
int i,w,u,v;
while(~scanf("%d%d",&m,&n)){
cnt=1;memset(hd,0,sizeof(hd));
s=1;t=n;
for(i=0;i<m;i++)scanf("%d%d%d",&u,&v,&w),add(u,v,w);
printf("%lld\n",dinic());
}
return 0;
}
F POJ 2396 - Budget
题目描述
给一个网格图填数，给一些大小限制和行列总和，求解。
解题思路
上下界网络流，把行列都当做点看即可。
AC代码
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
typedef long long ll;
using namespace std;
struct Edge{
int l,e,n;
}e[P*P];
int hd[P],cur[P],cnt=1;
int inf=1e9;
int n,m,s,t,ss,tt;
ll sum;
int dep[P];
queue<int>Q;
int dfs(int p,int flow){
if(p==t)return flow;
int i;
for(i=cur[p];i;i=e[i].n){
int q=e[i].e;
cur[p]=i;
if(dep[q]>dep[p]&&e[i].l){
int ans=dfs(q,min(flow,e[i].l));
if(ans){
e[i].l-=ans;
e[i^1].l+=ans;
return ans;
}
}
}
return 0;
}
int bfs(){
memset(dep,0,sizeof(dep));
Q.push(s);dep[s]=1;
int i;
while(!Q.empty()){
int p=Q.front();Q.pop();
for(i=hd[p];i;i=e[i].n){
int q=e[i].e;
if(!dep[q]&&e[i].l)dep[q]=dep[p]+1,Q.push(q);
}
}
return dep[t];
}
ll dinic(){
int i,d;
ll ans=0;
while(bfs()){
for(i=0;i<=t;i++)cur[i]=hd[i];
while((d=dfs(s,inf)))ans+=d;
}
return ans;
}
int lim[2][N][M],flag,full;
int ans[N][M];
void init (){
int i,j;
memset(lim[0],0,sizeof(lim[0]));
memset(lim[1],0x3f,sizeof(lim[1]));
memset(hd,0,sizeof(hd));
memset(ans,0,sizeof(ans));
cnt=1;
flag=0;
full=0;
}
void add(int a,int b,int l){
if(a==s)full+=l;
if(!l)return;
e[++cnt].e=b;e[cnt].l=l;e[cnt].n=hd[a];hd[a]=cnt;
e[++cnt].e=a;e[cnt].l=0;e[cnt].n=hd[b];hd[b]=cnt;
}
void ins(int a,int b,int low,int high){
if(high<low)flag=1;
add(s,b,low);
add(a,t,low);
add(a,b,high-low);
}
int main(){
int i,j,T,a,q;
scanf("%d",&T);
while(T--){
init();
scanf("%d%d",&n,&m);
ss=n+m+1;tt=ss+1;
s=tt+1;t=s+1;
for(i=1;i<=n;i++)scanf("%d",&a),ins(ss,i,a,a);
for(i=1;i<=m;i++)scanf("%d",&a),ins(i+n,tt,a,a);
scanf("%d",&q);
while(q--){
char s[5]={0};
int u,v,l1,r1,l2,r2;
scanf("%d%d%s%d",&u,&v,s,&a);
if(!u)l1=1,r1=n;else l1=r1=u;
if(!v)l2=1,r2=m;else l2=r2=v;
for(i=l1;i<=r1;i++)for(j=l2;j<=r2;j++){
if(s[0]=='<')lim[1][i][j]=min(lim[1][i][j],a-1);
if(s[0]=='>')lim[0][i][j]=max(lim[0][i][j],a+1);
if(s[0]=='=')lim[0][i][j]=max(lim[0][i][j],a),lim[1][i][j]=min(lim[1][i][j],a);
}
}
for(i=1;i<=n;i++)for(j=1;j<=m;j++)ins(i,j+n,lim[0][i][j],lim[1][i][j]);
ins(tt,ss,0,inf);
if(flag||dinic()!=full){
printf("IMPOSSIBLE\n\n");
continue;
}
for(i=2;i<=cnt;i++)
if(e[i^1].e>=1&&e[i^1].e<=n&&e[i].e>=n+1&&e[i].e<=n+m)
ans[e[i^1].e][e[i].e-n]=e[i^1].l;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)printf("%d ",ans[i][j]+lim[0][i][j]);
puts("");
}
puts("");
}
return 0;
}
G POJ 3020 - Antenna Placement
题目描述
给一个$o$（空地）和$*$（城市）组成的图，一个基站可以覆盖相邻的两个城市，问至少要多少基站才能覆盖所有城市。
解题思路
相邻城市建边跑二分图最大匹配即可，假设开始一个城市对应一个基站，则每一个匹配对应一个基站的减少，答案为城市数$-$最大匹配数。
AC代码
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
struct Edge{int e,n;}e[M];
int hd[N],mt[N],cnt,vis[N];
int mp[N][N];
void add(int a,int b){e[++cnt].e=b;e[cnt].n=hd[a];hd[a]=cnt;}
int dfs(int p,int t){
int i;
for(i=hd[p];i;i=e[i].n){
int q=e[i].e;
if(vis[q]!=t){
vis[q]=t;
if(!mt[q]||dfs(mt[q],t))return mt[q]=p;
}
}
return 0;
}
int maxmt(int n){
int i,ans=0;
for(i=1;i<=n;i++)
if(dfs(i,i))ans++;
return ans;
}
char a[N];
int main(){
int i,j,n,m,t;
scanf("%d",&t);
while(t--){
int lcnt=0,rcnt=0,tot=0;
memset(hd,0,sizeof(hd));cnt=0;
memset(vis,0,sizeof(vis));
memset(mt,0,sizeof(mt));
memset(mp,0,sizeof(mp));
scanf("%d%d",&n,&m);
for(i=0;i<n;i++){
scanf("%s",a);
for(j=0;a[j];j++){
if(a[j]=='*'){
if((i+j)&1)mp[i][j]=++lcnt;
else mp[i][j]=++rcnt;
++tot;
}
}
}
for(i=0;i<n;i++){
for(j=0;j<m;j++){
if(mp[i][j]&&((i+j)&1)){
if(i&&mp[i-1][j])add(mp[i][j],mp[i-1][j]);
if(i+1<n&&mp[i+1][j])add(mp[i][j],mp[i+1][j]);
if(j+1<m&&mp[i][j+1])add(mp[i][j],mp[i][j+1]);
if(j&&mp[i][j-1])add(mp[i][j],mp[i][j-1]);
}
}
}
printf("%d\n",tot-maxmt(lcnt));
}
return 0;
}