摘要:负权费用流思路

[网络流24题]魔术球问题

题面

题目分析

这个思路特别地鬼怪.

首先将和为完全平方数的数字小的向大的连边,流量为inf.

现在考虑将这些数字分成n个集合,所以将源点拆点,连一条流量为n的边,数字拆点,连一条流量为1的边,出点连向汇点,入点连向源点的出点.

这样一条增广路就对应了一个柱子上放的数.

但是我们要这条增广路尽量地长,才能保证取到的数字连续,因为显然数字越小与它连边的数越多,尽可能地长的路径就可以取到更多的数.

通过找规律发现柱子上的完全平方数最大为n*n,所以处理一下防止增广到后面的大数,没想到证明方法不过规律挺容易就发现了.

所以将数字拆点之间的边设定费用为-1,这样就会增广更多的数来得到最小费用,最小费用取反即为答案.

现在问题是如何输出数字连续的方案,从汇点开始递归,遍历虚边上流量为1的边,建模的方式可以保证路径上的向源点方向单调减少,所以一直向前输出即可.

但是需要注意的是可能出现有一个柱子上只放了一个数,这条增广路可能由后面的点得到,所以汇点开始遍历的时候除去大于答案的数,之后输出在$[1,ans]$中没有输出的数到这个柱子对应的方案上.

代码

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
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
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 4557430888798830399
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl small=6060,big=100010;
lxl n,EdgeSize,s,ss,t,MinCost,yag;
lxl head[small],cur[small],dis[small],vis[small],po[60],flag[big];
std::queue<lxl>q;
struct _Edge
{
lxl next,v,w,flow;
}e[big];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
inline void EdgeAdd(lxl u,lxl v,lxl flow,lxl w)
{
e[EdgeSize].v=v;
e[EdgeSize].next=head[u];
e[EdgeSize].flow=flow;
e[EdgeSize].w=w;
head[u]=EdgeSize++;
}
inline bool SPFA()
{
memset(vis,0,sizeof vis),memset(dis,INF,sizeof dis);
// debug(dis[1]);return false;
memcpy(cur,head,sizeof cur);
dis[s]=0,vis[s]=true,q.push(s);
for(;!q.empty();)
{
lxl u=q.front();q.pop(),vis[u]=false;
for(R int i(head[u]);~i;i=e[i].next)
{
lxl v=e[i].v,w=e[i].w,fl=e[i].flow;
if(fl>0&&dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
if(!vis[v])vis[v]=true,q.push(v);
}
}
}
return dis[t]<INF;
}
lxl dfs(lxl u,lxl flow)
{
if(u==t)return flow;
lxl sum(0);
vis[u]=true;
for(R lxl &i(cur[u]);~i;i=e[i].next)
{
lxl v=e[i].v,fl=e[i].flow,w=e[i].w;
if(fl>0&&!vis[v]&&dis[v]==dis[u]+w)
{
lxl delta=dfs(v,std::min(flow-sum,fl));
e[i].flow-=delta,e[i^1].flow+=delta;
sum+=delta,MinCost+=delta*w;
if(sum==flow)return sum;
}
}
vis[u]=false;
return sum;
}
inline void dinic()
{
for(;SPFA();)for(;dfs(s,INF););
}
inline void init()
{
for(R int i(2);i<=n;++i)po[++po[0]]=i*i;
memset(head,-1,sizeof head);
EdgeSize=0;
EdgeAdd(s,ss,n,0),EdgeAdd(ss,s,0,0);
for(R int i(1);i<=yag;++i)EdgeAdd(i,i+yag,1,-1),EdgeAdd(i+yag,i,0,1);
for(R int i(1);i<=yag;++i)
{
EdgeAdd(ss,i,INF,0),EdgeAdd(i,ss,0,0);
EdgeAdd(i+yag,t,INF,0),EdgeAdd(t,i+yag,0,0);
}
for(R int i(1);i<=yag;++i)
for(R int j(po[0]);j;--j)
if(i*2<po[j])EdgeAdd(i+yag,po[j]-i,INF,0),EdgeAdd(po[j]-i,i+yag,0,0);
}
void print(lxl u)
{
// if(u==ss)return;
u-=yag;
printf("%lld ",u);flag[u]=true;
for(R int i(head[u]);~i;i=e[i].next)
if(e[i].flow==1&&e[i].v!=ss){print(e[i].v);}
}
int main(void)
{
// freopen("data.txt","r",stdin);
// freopen("out","w",stdout);
n=read();yag=n*n;
// debug(yag);
s=yag+yag+1,ss=yag+yag+2,t=yag+yag+3;
init();
dinic();
printf("%lld\n",-MinCost);
// for(R int i(head[690]);~i;i=e[i].next)if(e[i].flow==1)debug(e[i].v-yag);
for(R int i(head[t]);~i;i=e[i].next)
if(e[i].flow==1&&e[i].v-yag<=-MinCost)print(e[i].v),endl;
for(R int i(1);i<=-MinCost;++i)if(!flag[i])printf("%d ",i);endl;
return 0;
}