[Topcoder SRM 590]Fox And City(网络流建模)

题面

问题描述：
一个国家有n个城市，编号为0~n-1。编号为0的城市是首都。该国的道路网形成无向连通图。换句话说：城市之间通过双向路径连接。
对于每个城市，至少有一条从该城市到首都的路径(path)。路径是由许多连续的道路(road)组成的，路径只在城市有交汇点。
两个城市之间的距离是指这两个城市之间的最小道路数。
居住在其他城市的人们通常对他们所在城市与首都的距离不满。want[i]是城市i和首都（城市0）之间的期望距离。
小明负责修建新道路。每条新道路必须是双向的并且直接连接两个城市。用real [i]表示城市i和首都之间的新距离。新道路建成后，市民将用不开心指数评估他们对最终道路的满意度。不开心指数表示为（want[i]-real[i]）^2。
你的任务是帮助小明设计一个新道路建造方案（也可以不建），使得所有城市的不开心指数之和最小。
$10<=n<=40$
加强版:$10<=n<=100$

题解

emmm…直觉挺准的，是一道网络流的题，然而就是不会建图…

好像是自己忘了网络流还可以求最小割???
自闭…
首先可以考虑一下BFS的性质:只会出现横向边。
也就是说，设$dis[i]$为$i$点与$0$号点的最短距离。
若为横向边$dis[u]=dis[v]$,否则$|dis[u]?dis[v]|=1$
总结一下就是$|dis[u]?dis[v]|\le 1$
然后还可以发现的是，$dis[i]$只可能变小，也就是说$di{s}^{\prime }[i]\le dis[i]$
发现限制是同号的…可以尝试一下网络流。

建立源点S，汇点T。将原图中每个节点i拆成n个点，point(i,k)(0≤k≤n-1)，令节点point(i,k)
表示 distance[i]<=k。若最小割中，节点 point(i,k)在 S 集中，代表 distance[i]<=k 为 false，
否则为 true。构图方法如下：
1，从 S 向 point(i,0)(1≤i≤n-1)连一条容量为正无穷的边。除节点 0 外的所有节点权值均
不可能为 0。
2，从每个 point(i,n-1)(0≤i≤n-1)向 T 连一条容量为正无穷的边。任意节点的 distance 值
均不超过 n-1。
3，从 point(i,k)向 point(i,k+1)一条容量为((k+1)-want[i])^2(若 i=0,这条边的容量为正无
穷)。可以用这条边容量的代价将 point(i,k)和 point(i,k+1)分到两个不同的集合。

4，显然，若 point(i,k)为 false，point(i,k-1)必然也为 false，因此从每个 point(i,k)向
point(i,k-1)连一条权值为正无穷的边。
5，对于原图中的每条边(i,j)，因为|dis[u]-dis[v]|≤1。所以若 point(i,k)为 false，
必然有 point(j,k-1)为 false。所以从每个 point(i,k)向 point(j,k-1)连一条容量为正无穷的边，
从每个 point(j,k)向 point(i,k-1)连一条容量为正无穷的边。

由于蒟蒻懒得打字，感谢Transcendence_magia大佬对topcoder题解的翻译[虽然看上去并不像翻译]
原文链接

这样建图就可以完美的解决这个问题了…
然而还是有复杂度的问题
这样建图的点数是$O(n^2)$，边数为$O(n^3)$。
如果按上界$O(n^{2}m)$来算的话完全过不了。
然而实际上并不是这样…根据洛谷模板所示，当前弧优化的Dinic最慢可以在1s内跑完$点数<=10000,边数<=100000$的数据范围。
照这样算点数大约是1600个,边数大约64000条,是在可行范围内的。
然而实测结果是，算法可以在1s内跑完$n\le 100$的数据规模。
这是因为实际访问的边数为$O(n^2)$而造成的，因为仅有$|dis[u]?dis[v]|=1$时，上文中的第5种边才会被访问到。
这样算点数大约是10000个,边数大约10000条,完全是网络流可以接受的范围。
[注:为了连边方便,代码实现的连边方式与上述连边方式有微小差异,在代码中已标注]

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define MAXN 20000
#define MAXE 100
#define MAXM 1000000
#define INF 1000000000
int n,S,T;
int head[MAXN+5],cur[MAXN+5];
int dep[MAXN+5],want[MAXN+5],ecnt,pcnt;
int mp[MAXE+5][MAXE+5],id[MAXE+5][MAXE+5];
char s[MAXN+5];
int read()
{
    int F=1,x=0;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=x*10+c-'0';c=getchar();}return x;
}
void Init()
{
    ecnt=1;memset(head,-1,sizeof(head));}
struct edge
{
    int to,nxt,cap;
}e[MAXM*2+5];
void add(int u,int v,int cap)
{
    e[++ecnt]=(edge){
    v,head[u],cap};head[u]=ecnt;e[++ecnt]=(edge){
    u,head[v],0};head[v]=ecnt;
}
int BFS()
{
    for(int i=S;i<=T;i++)dep[i]=0,cur[i]=-1;queue<int> Q;Q.push(S);dep[S]=1;while(!Q.empty()){
    int x=Q.front();Q.pop();for(int i=head[x];i!=-1;i=e[i].nxt){
    int xnt=e[i].to;if(dep[xnt]||!e[i].cap)continue;dep[xnt]=dep[x]+1;Q.push(xnt);}}return dep[T];
}
int dinic(int x,int Flow)
{
    if(x==T)return Flow;int pcap=Flow;if(cur[x]==-1)cur[x]=head[x];for(int &i=cur[x];i!=-1;i=e[i].nxt){
    int xnt=e[i].to;if(dep[x]+1!=dep[xnt]||!e[i].cap)continue;int pe=dinic(xnt,min(e[i].cap,pcap));e[i].cap-=pe,e[i^1].cap+=pe;pcap-=pe;if(!pcap)break;}return Flow-pcap;
}
void Build_G()
{
    //将限制dep[1]=0改成了限制1的儿子的dep为1 for(int i=1;i<=n;i++){
    if(i!=1){
    for(int j=1;j<=n;j++)if(j==1)add(S,id[i][j],(want[i]-1)*(want[i]-1));else {
    if(!mp[i][1])add(id[i][j-1],id[i][j],(want[i]-j)*(want[i]-j));else add(id[i][j-1],id[i][j],INF);}add(id[i][n],T,INF);}for(int j=2;j<=n;j++)if(mp[i][j]){
    for(int k=2;k<=n;k++)add(id[i][k],id[j][k-1],INF);}}
}
int main()
{
    freopen("newroad.in","r",stdin);freopen("newroad.out","w",stdout);Init();n=read();S=0,T=n*n+1;for(int i=1;i<=n;i++){
    scanf("%s",s+1);for(int j=1;j<=n;j++){
    if(s[j]=='Y')mp[i][j]=1;id[i][j]=++pcnt;}}for(int i=1;i<=n;i++)scanf("%d",&want[i]);Build_G();int ans1=0;while(BFS()){
    ans1+=dinic(S,INF);}printf("%d",ans1+want[1]*want[1]);
}