题目大意
给一张联通无向图，定义$Dist[i][j]$表示点$i$到点$j$之间的最短路。当前已经有了若干条的边，再给定$N$个$A[i]$，要求添加若干条无向边，使得$\sum(a[i]-Dist[1][i])^2$最小。输出最小的答案。
题目分析
这道题出的很好！
首先我们将问题抽象为线性规划问题。
因为原图边权均为$1$，对于原图的每一条边$(u\leftrightarrow v)$，若存在$\left|dist[1,u]-dist[1,v]\le1\right|$，则一定存在一个合法的建图方案。
故我们将问题抽象为了：有权值限制，使得目标函数最小化的线性规划问题。当然可以用单纯形解决。
更一般的，我们可以采用离散变量模型解决该问题，即通过离散变量取值间建边达到限制的目的。（切糕就是一道经典例题）
虽然点数较多，但是跑得很快。
当然考试的时候我并没有想到这种做法（achen太强了），然后我发现这道题类似均分数据，限制条件不多，但要求权值很怪。
因此可以上模拟退火/爬山算法进行乱搞。
考试时退了$1000$次火，拿了$80$分，改成$4000$就可以过了。奇慢无比
代码
网络流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
131
132
133
134
135
136
137
138
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
struct Edge {
int from,to,cap,flow;
Edge(int x=0,int y=0,int c=0,int f=0):from(x),to(y),cap(c),flow(f) {}
};
struct Dinic {
const static int maxn=70005;
int n,m,s,t;
vector<Edge>edges;
vector<int>G[maxn];
bool vst[maxn];
int dist[maxn],cur[maxn];
void init(int n) {
this->n=n;
edges.clear();
for(int i=1; i<=n; i++)G[i].clear();
}
void AddEdge(int x,int y,int v) {
edges.push_back(Edge(x,y,v,0));
edges.push_back(Edge(y,x,0,0));
m=edges.size();
G[x].push_back(m-2);
G[y].push_back(m-1);
}
bool bfs() {
memset(vst,0,sizeof(vst));
memset(dist,0,sizeof(dist));
queue<int>Q;
Q.push(t);
vst[t]=1;
while(!Q.empty()) {
int Now=Q.front();
Q.pop();
for(int id:G[Now]) {
Edge& e=edges[id^1];
int Next=e.from;
if(!vst[Next]&&e.cap>e.flow) {
vst[Next]=1;
dist[Next]=dist[Now]+1;
Q.push(Next);
}
}
}
return vst[s];
}
int dfs(int Now,int a) {
if(Now==t||a==0)return a;
int flow=0;
for(int& i=cur[Now]; i<G[Now].size(); i++) {
Edge& e=edges[G[Now][i]];
int Next=e.to;
if(dist[Now]-1!=dist[Next])continue;
int nextflow=dfs(Next,min(a,e.cap-e.flow));
if(nextflow>0) {
e.flow+=nextflow;
edges[G[Now][i]^1].flow-=nextflow;
flow+=nextflow;
a-=nextflow;
if(a==0)break;
}
}
return flow;
}
int maxflow(int s,int t) {
this->s=s;
this->t=t;
int flow=0;
while(bfs()) {
memset(cur,0,sizeof(cur));
flow+=dfs(s,INT_MAX);
}
return flow;
}
} dinic;
const int maxn=45;
int n,cnt=0,a[maxn],id[maxn][maxn],map[maxn][maxn];
int main() {
n=Get_Int();
for(int i=1; i<=n; i++)
for(int j=0; j<=n; j++)
id[i][j]=++cnt;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) {
char opt=' ';
while(!isalpha(opt))opt=getchar();
if(opt=='Y')map[i][j]=1;
}
int S=cnt+1,T=cnt+2;
for(int i=1; i<=n; i++)a[i]=Get_Int();
dinic.AddEdge(S,id[1][0],0);
for(int j=1; j<=n; j++)dinic.AddEdge(id[1][j-1],id[1][j],INT_MAX);
dinic.AddEdge(id[1][n],T,INT_MAX);
for(int i=2; i<=n; i++) {
dinic.AddEdge(S,id[i][0],INT_MAX);
for(int j=1; j<=n; j++)dinic.AddEdge(id[i][j-1],id[i][j],sqr(a[i]-j));
dinic.AddEdge(id[i][n],T,INT_MAX);
}
for(int i=1; i<=n; i++)
for(int j=i+1; j<=n; j++)
if(map[i][j])
for(int k=0; k<=n; k++) {
dinic.AddEdge(id[i][k+1],id[j][k],INT_MAX);
dinic.AddEdge(id[j][k+1],id[i][k],INT_MAX);
}
printf("%d\n",dinic.maxflow(S,T));
return 0;
}
退火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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=55;
struct Graph {
int n;
bool map[maxn][maxn];
vector<int>edges[maxn];
void init(int n) {
this->n=n;
}
void AddEdge(int x,int y) {
edges[x].push_back(y);
map[x][y]=1;
}
struct QueNode {
int d,u;
bool operator < (const QueNode& b) const {
return d>b.d;
}
};
int Dist[maxn];
bool vst[maxn];
void dijkstra(int s) {
for(int i=1; i<=n; i++)Dist[i]=1000;
memset(vst,0,sizeof(vst));
priority_queue<QueNode>Q;
Dist[s]=0;
Q.push((QueNode) {0,s});
while(!Q.empty()) {
int Now=Q.top().u;
Q.pop();
if(vst[Now])continue;
vst[Now]=1;
for(int Next:edges[Now])
if(Dist[Next]>Dist[Now]+1) {
Dist[Next]=Dist[Now]+1;
Q.push((QueNode) {Dist[Next],Next});
}
}
}
} G;
int n,a[maxn],From[maxn*maxn],To[maxn*maxn],S,Ans=INT_MAX;
namespace Solve1 {
void solve() {
int cnt=0;
for(int i=1; i<=n; i++)
for(int j=i+1; j<=n; j++)
if(!G.map[i][j]) {
cnt++;
From[cnt]=i;
To[cnt]=j;
}
for(int S=1; S<(1<<cnt); S++) {
Graph tmp=G;
for(int i=1; i<=cnt; i++)
if(S&(1<<(i-1))) {
tmp.AddEdge(From[i],To[i]);
tmp.AddEdge(To[i],From[i]);
}
tmp.dijkstra(1);
int sum=0;
for(int i=1; i<=n; i++)sum+=(a[i]-tmp.Dist[i])*(a[i]-tmp.Dist[i]);
if(sum<Ans)Ans=sum;
}
}
}
namespace Solve2 {
const double START_T=10000,END_T=1e-2,DELTA=0.9,P=0.2;
int Anneal() {
srand(time(NULL));
int ans=S,Min=S;
double t=START_T;
Graph Now=G;
while(t>END_T) {
int cnt=0;
for(int i=1; i<=n; i++)
for(int j=i+1; j<=n; j++)
if(!Now.map[i][j]) {
cnt++;
From[cnt]=i;
To[cnt]=j;
}
if(cnt==0)break;
int choose=rand()%cnt;
Graph tmp=Now;
tmp.AddEdge(From[choose],To[choose]);
tmp.AddEdge(To[choose],From[choose]);
tmp.dijkstra(1);
int sum=0;
for(int i=1; i<=n; i++)sum+=(a[i]-tmp.Dist[i])*(a[i]-tmp.Dist[i]);
if(sum<ans||exp(-t/START_T)<P) {
ans=sum;
Now=tmp;
}
Min=min(Min,sum);
t*=DELTA;
}
return Min;
}
void solve() {
for(int i=1; i<=4000; i++)Ans=min(Ans,Anneal());
}
}
int main() {
n=Get_Int();
G.init(n);
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) {
char x=' ';
while(!isalpha(x))x=getchar();
if(x=='Y')G.AddEdge(i,j);
}
for(int i=1; i<=n; i++)a[i]=Get_Int();
G.dijkstra(1);
for(int i=1; i<=n; i++)S+=(a[i]-G.Dist[i])*(a[i]-G.Dist[i]);
Ans=S;
if(n<=4)Solve1::solve();
else Solve2::solve();
printf("%d\n",Ans);
return 0;
}
