「泉七培训 – 杨国烨」图
「题目描述」
给一张联通无向图，定义Dist[i][j]表示点i到点j之间的最短路。当前已经有了若干条的边，再给定N个A[i]，要求添加若干条无向边，使得Σ(a[i] – Dist[1][i])^2最小。输出最小的答案。
「输入格式」
第一行是整数N，表示节点数。
接下来是N*N的矩阵，mat[i][j] = ‘Y’表示i和j之间有一条无向边。保证mat[i][j] = mat[j][i]。
接下来N个数，表示A[i]。
「输出格式」
求答案。
「样例输入」
4
NYNN
YNYN
NYNY
NNYN
0 3 3 3
「样例输出」
5
「样例解释」
不用额外建任何边了233
「数据规模和约定」
对于10%的数据，N<=4。
对于100%的数据，2<=N<=40。
题解
orz cxjyxx_me
最短路满足|Dist[i] – Dist[j]| <= 1，0号节点的Dist一定是0。其他的一定>=1。
因为可以任意添加边，所以任意一组满足上面的条件的dist都是合法的。←自己证明吧，不算难。所以我们现在的问题就是，我们要给每一个节点指定一个dist，满足对于原图的任意一条边，|Dist[i]-Dist[j]|<=1。要求最小化Σ(Dist[i]-A[i])^2。
拆开绝对值，就是Dist[i]-Dist[j]<=1，并且Dist[j]-Dist[i]<=1。每一个限制都可以理解为:如果i取了Dist[i]的话，j至少得取Dist[i]-1以上。
我们用网络流模型来刻画这个东西。
因为dist的取值只有N种，我们对于每个点，拆成N个点。
(i, j) -> (i, j + 1) 容量为(A[i] – j)^2，
对于原图的一条边(u, v)
对于所有的j，
连接(u, j) -> (v, j – 1), (v, j) ->(u, j – 1)，容量均为正无穷。
考虑这个图的割，很显然它只可能割在第一种的边上。
因为我们连接了(u, j) ->(v, j – 1)，那么很显然如果u这个点割在了(u, j)->(u, j+1)的话，v至少得割一条>=j-1的边才能满足没有增广路。所以构图成立，直接跑最小割即可。
注意特判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 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #define inf 0x7fffffff #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int sqr(int x){return x*x;} int n,cnt=1,T,ans,a[55]; int last[2505],h[2505],q[2505]; int p[55][55]; bool mp[55][55]; struct data{int to,next,v;}e[20005]; void insert(int u,int v,int w) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0; } bool bfs() { int head=0,tail=1; memset(h,-1,sizeof(h)); q[0]=0;h[0]=0; while(head!=tail) { int now=q[head];head++; for(int i=last[now];i;i=e[i].next) if(e[i].v&&h[e[i].to]==-1) { h[e[i].to]=h[now]+1; q[tail++]=e[i].to; } } return h[T]!=-1; } int dfs(int x,int f) { if(x==T)return f; int w,used=0; for(int i=last[x];i;i=e[i].next) if(h[e[i].to]==h[x]+1) { w=dfs(e[i].to,min(f-used,e[i].v)); e[i].v-=w;e[i^1].v+=w; used+=w;if(used==f)return f; } if(!used)h[x]=-1; return used; } void dinic() { while(bfs())ans+=dfs(0,inf); } void build() { for(int i=1;i<=n;i++) { if(i==1) { insert(0,p[i][1],0); for(int j=1;j<=n;j++) insert(p[i][j],p[i][j+1],inf); insert(p[i][n+1],T,inf); } else { insert(0,p[i][1],inf); for(int j=1;j<=n;j++) insert(p[i][j],p[i][j+1],sqr(a[i]-j)); insert(p[i][n+1],T,inf); } } for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(mp[i][j]) for(int k=1;k<=n;k++) { insert(p[j][k+1],p[i][k],inf); insert(p[i][k+1],p[j][k],inf); } } int main() { n=read(); for(int i=1;i<=n;i++) for(int j=1;j<=n+1;j++) p[i][j]=++T; T++; for(int i=1;i<=n;i++) { char ch[50]; scanf("%s",ch); for(int j=1;j<=n;j++) if(ch[j-1]=='Y')mp[i][j]=1; } for(int i=1;i<=n;i++)a[i]=read(); build(); dinic(); printf("%d",ans); return 0; } |
OI 课件=>
