Topcoder SRM 590 Fox And City

Link

注意到原图给的是一个无向连通图。

如果在原图中两点之间有一条无向边，那么这两点到\(1\)的距离之差不大于\(1\)。

这个命题的正确性是显然的，我们考虑它的逆命题：

给定每个点到\(1\)的距离（不大于\(n\)），并给定一些已有的边，满足已有的边的两端到\(1\)的距离之差不大于\(1\)，那么一定存在一种方案满足该种情况。

因为题目给的是一个无向连通图，所以我们可以先构造一条最短路径递增的链，然后再把其它的点挂在上面即可。

那么现在就变成了距离限制模型，直接最小割即可。

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm>

int read(){int x;scanf("%d",&x);return x;}

const int N=47,V=2007,E=150007,inf=1e9;

int n,s,t,tot=1,e[N][N],w[N],head[V],ver[E],next[E],edge[E],cur[V],dep[V];std::queue<int>q;

int sqr(int a){return a*a;}

void add(int u,int v,int w){ver[++tot]=v,next[tot]=head[u],edge[tot]=w,head[u]=tot,ver[++tot]=u,next[tot]=head[v],edge[tot]=0,head[v]=tot;}

int bfs()

{

    memset(dep+1,0x3f,t<<2),memcpy(cur+1,head+1,t<<2),dep[s]=0,q.push(s);

    for(int i,u,v;!q.empty();) for(u=q.front(),q.pop(),i=head[u];i;i=next[i]) if(dep[v=ver[i]]>inf&&edge[i]) dep[v]=dep[u]+1,q.push(v);

    return dep[t]<inf;

}

int dfs(int u,int lim)

{

    if(!lim||u==t) return lim;

    int v,flow=0;

    for(int&i=cur[u],f;i;i=next[i])

        if(dep[v=ver[i]]==dep[u]+1&&(f=dfs(v,std::min(lim,edge[i]))))

        {

            flow+=f,lim-=f,edge[i]-=f,edge[i^1]+=f;

            if(!lim) break;

        }

    return flow;

}

int dinic(){int ans=0;while(bfs()) ans+=dfs(s,inf);return ans;}

int solve()

{

    s=n*n+1,t=s+1;

    for(int i=1;i<=n;++i)

    {

	add(s,(i-1)*n+1,i==1? 0:inf),add(i*n,t,inf);

	for(int j=1;j<n;++j) add((i-1)*n+j,(i-1)*n+j+1,i==1? inf:sqr(w[i]-j));

	for(int j=1;j<=n;++j) if(e[i][j]) for(int k=1;k<n;++k) add((i-1)*n+k+1,(j-1)*n+k,inf);

    }

    return dinic();

}

class FoxAndCity

{

public:

    int minimalCost(std::vector<std::string>g,std::vector<int>vec)

    {

	n=g.size();

	for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) e[i][j]=g[i-1][j-1]=='Y';

	for(int i=1;i<=n;++i) w[i]=vec[i-1];

	return solve();

    }

};

巴特西

Topcoder SRM 590 Fox And City

最新文章

热门文章