TopCoder12727 「SRM590Hard」FoxAndCity 最小割离散变量模型

问题描述

一张 \(N\) 个点无向图，边权都为 \(1\) ，添加若干条边，最小化 \(\sum\limits_{1 \le i \le n,i \in N_{+}}{(a_i-b_i)^2}\)。 \(b_i\) 是输入的， \(a_i\) 是 \(1\) 号点到 \(i\) 号点的最短路。

submit

---

题解

添加边后， \(a_i\) 不会变小。

\(a_i\) 就是离散变量。

原来有边的两个点 \(x,y\) 的最短路长度差值不会超过 \(1\) 。

---

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;const int INF=0x3f3f3f3f;//#define local
//#define fileint n,b[47],S,T;
char s[47][47];int Head[2507],d[2507];
int to[500007],Next[500007],w[500007],tot=1;void addedge(int x,int y,int z){
to[++tot]=y,Next[tot]=Head[x],Head[x]=tot,w[tot]=z;
}void add(int x,int y,int z){
addedge(x,y,z);addedge(y,x,0);
}void Init(void){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
}int dis[2507],sum[2507];
bool vis[2507];
#define pii(x,y) make_pair(x,y)void dijkstra(){
memset(dis,0x3f,sizeof(dis));
priority_queue < pair<int,int> > q;
dis[1]=0;q.push(pii(0,1));
while(!q.empty()){
int x=q.top().second;q.pop();
if(vis[x]) continue;
vis[x]=1;
for(int i=1;i<=n;i++){
if(s[x][i]=='N') continue;
if(dis[i]>dis[x]+1){
dis[i]=dis[x]+1;
q.push(pii(-dis[i],i));
}
}
}
}int id(int x,int y){
return (x-1)*n+y;
}void debug(void){
for(int i=2;i<=tot;i+=2){
printf("-- From %d to %d w = %d \n",to[i^1],to[i],w[i]);
}
printf("## S = %d , T = %d\n",S,T);
}void Graph_build(void){
//dijkstra();
//for(int i=1;i<=n;i++) sum[i]=sum[i-1]+dis[i]+1;
S=n*n+1,T=S+1;
add(1,T,INF);//错误笔记：1号点最短路为零，为了防止S->1->T不能正常加边，但是1->T还是得加
for(int i=2;i<=n;i++){
add(S,id(i,1),INF);
for(int j=1;j<n;j++){
int price=(j-b[i])*(j-b[i]);
add(id(i,j),id(i,j+1),price);
}
add(id(i,n),T,INF);
}
for(int x=1;x<=n;x++){
for(int y=1;y<=n;y++){
if(s[x][y]=='N') continue;
//int lim=min(dis[x],dis[y]);
for(int i=1;i<n;i++){
add(id(x,i+1),id(y,i),INF);
}
}
}
//debug();
}bool bfs(void){
memset(d,0,sizeof(d));
queue<int>q;q.push(S);d[S]=1;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=Head[x];i;i=Next[i]){
int y=to[i];
if(d[y]||!w[i]) continue;
d[y]=d[x]+1;q.push(y);
if(y==T) return true;
}
}
return false;
}int dfs(int x,int flow){
if(x==T) return flow;
int rest=flow;
for(int i=Head[x];i;i=Next[i]){
int y=to[i];
if(d[y]!=d[x]+1||!w[i]) continue;
int k=dfs(y,min(rest,w[i]));
if(!k) d[y]=0;
else w[i]-=k,w[i^1]+=k,rest-=k;
}
return flow-rest;
}int Dinic(void){
int res(0),t;
while(bfs()){
while(t=dfs(S,INF)) res+=t;
}
return res;
}int Work(void){
Graph_build();
return Dinic();
}#ifndef local
class FoxAndCity{
public:
int minimalCost(vector<string>str,vector<int>in){
n=str[0].size();
for(int i=0;i<n;i++){
b[i+1]=in[i];
for(int j=0;j<n;j++){
s[i+1][j+1]=str[i][j];
}
}
return Work();
}
};
#endif#ifdef local
int main(){
#ifdef file
freopen("hzlbn.in","r",stdin);
#endif
Init();
printf("%d\n",Work());
return 0;
}
#endif