题解：UVA10276 Hanoi Tower Troubles Again!

· · 题解

1.28 修改了一些笔误，重新提交。

唯一一篇非贪心题解。

UVA10276 Hanoi Tower Troubles Again!

前置知识：P2764 最小路径覆盖问题。

双倍经验：P2765 魔术球问题。这俩编号怎么只相差一。

分析

Part 1：如何建模

我们考虑对于数 i,j(i<j)，如果 i+j 是完全平方数，那么就连边。

可以发现这就是构成了一个有向无环图。

Part 2：如何根据球的数量计算柱子

其实，这就是一个最小路径覆盖。

让我们看样例的一个构造方案：

11
1 8
2 7 9
3 6 10
4 5 11

看出来了吗，这些颜色就是柱子上放的数！

当然，还有另一种构造方案：

其中 1 号点颜色不同。

Part 3：如何计算路径覆盖

由于我们懒得写网络流，于是我们翻出了匈牙利。

参见我写的：【最小路径覆盖问题】。

我们先进行拆点，将 u 拆成 u_{in},u_{out}。

根据 Dilworth 推广定理：最小路径覆盖数 = 顶点数 − 最大匹配数。

所以我们只需要跑二分图最大匹配了。

for(int i=0;i<m;i++){
    int u,v;
    cin>>u>>v;
    G[u].push_back(v);//这里实际上是拆点了
}

为什么这里拆点了呢？其实左边的 u 是 u_{out}，v 就是 v_{in}。

Part 4：如何根据柱子的数量计算球

考虑二分球的数量。与 n 比较大小即可。

bool check(int mid){
    if(solve(mid)<=n)return 1;
    return 0;
}
int l=1,r=M,mid;
while(l<=r){
    mid=(l+r)>>1;
    if(check(mid))l=mid+1,now=mid;
    else r=mid-1;
    // cout<<l<<' '<<r<<endl;
}
if(check(now-1))now++;
if(!check(now-1))now--;
cout<<now-1<<endl;

我们发现边数大约为 O(n^{3/2})，所以时间复杂度大约 O(n^{5/2}\log V)，V 可以取 2000。

当然你也可以不二分，直接枚举到 V，然后每次只加上新增的边跑二分图，这样是 O(n^{3/2}V) 的。

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000;
bool matched[maxn];
vector<int> G[maxn];
int match[maxn];
bool find(int u){
    for(auto v:G[u]){
        if(!matched[v]){
            matched[v]=1;
            if(!match[v]||find(match[v])){
                match[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
const int M=10000;
bool pd[M];
int solve(int ma){//根据球数算柱子
    for(int i=0;i<maxn;i++)G[i].clear();
    for(int i=1;i<=ma;i++){
        for(int j=i+1;j<=ma;j++){
            if((int)sqrt(i+j)*(int)sqrt(i+j)==i+j){
                G[i].push_back(j);//这里实际上是拆点了
            }
        }
    }
    int ans=0;
    memset(match,0,sizeof(match));
    for(int i=1;i<=ma;i++){
        memset(matched,0,sizeof(matched));
        if(find(i))ans++;
    }
    return ma-ans;
}
int pre[maxn],nxt[maxn],n;
bool vis[maxn];
bool check(int mid){
    if(solve(mid)<=n)return 1;
    return 0;
}
signed main(){
    int now=1;
    cin>>n;
    int l=1,r=M,mid;
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid))l=mid+1,now=mid;
        else r=mid-1;
        // cout<<l<<' '<<r<<endl;
    }
    if(check(now-1))now++;
    if(!check(now-1))now--;
    cout<<now-1<<endl;
    // for(int v=1;v<=now-1;v++){
    //  int u=match[v];
    //  if(u){
    //      nxt[u]=v;
    //      pre[v]=u;
    //  }
    // }
    // memset(vis,0,sizeof(vis));//标记顶点是否已被包含在路径中
    // vector<vector<int>>paths;//存储最终的所有路径
    // for(int u=1;u<=now-1;u++){
    //  if(pre[u]==0){
    //      vector<int> path;
    //      int v=u;
    //      while(v){
    //          vis[v]=1;
    //          path.push_back(v);
    //          v=nxt[v];
    //      }
    //      paths.push_back(path);
    //  }
    // }
    // for(auto &path:paths){
    //  for(int i=0;i<path.size();i++){
    //      cout<<path[i]<<' ';
    //  }
    //  cout<<endl;
    // }
    return 0;
}

Part 5：优化

还是上网络流。这样单轮时间复杂度是 O(m\sqrt n)=O(n^{3/2}\cdot n^{1/2})=O(n^2)，总计 O(n^2\log V)，完全可过。

#include<bits/stdc++.h>
using namespace std;
const int N=5055,M=125005,inf=2147483647;
int m,s,t;
int lvl[N];//层数
struct edge{
    int u,v,w;
    int nxt;
}ed[M*2];
int head[N],cur[N],cnt=2;
void adde(int u,int v,int w){
    ed[cnt].u=u;
    ed[cnt].v=v;
    ed[cnt].w=w; 
    ed[cnt].nxt=head[u];
    head[u]=cnt;
    cnt++; 
}
bool bfs(){
    queue<int> q;
    for(int i=0;i<N;i++)lvl[i]=-1;
    lvl[s]=0;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=ed[i].nxt){
            if(lvl[ed[i].v]==-1&&ed[i].w>0){
                lvl[ed[i].v]=lvl[u]+1;  
                q.push(ed[i].v);
                if(ed[i].v==t)return 1;
            }
        }
    }
    return(lvl[t]!=-1);
}
int dfs(int u,int cap){//cap:容量
    int flow=0;//跑过的流
    if(u==t)return cap;
    for(int i=cur[u];i&&cap;i=ed[i].nxt){
        cur[u]=i;
        int v=ed[i].v,w=ed[i].w;
        if(w&&lvl[v]==lvl[u]+1){
            int use=dfs(v,min(cap,w));
            if(use==0)lvl[v]=-1;
            if(use>0){
                ed[i].w-=use;
                ed[i^1].w+=use;
                cap-=use;
                flow+=use;
            }
        }
    }
    return flow;
}
int dinic(){
    int ans=0;
    while(bfs()){ 
        memcpy(cur,head,sizeof(head));
        ans+=dfs(s,inf);
    }
    return ans;
}
const int MM=2000;
bool pd[M];
int solve(int ma){//根据球数算柱子
    s=0,t=ma*2+1;
    cnt=2;
    memset(head,0,sizeof(head));
    memset(cur,0,sizeof(cur));
    for(int i=1;i<=ma;i++){
        adde(s,i,1);
        adde(i,s,0);
        adde(i+ma,t,1);
        adde(t,i+ma,0);
        for(int j=i+1;j<=ma;j++){
            if((int)sqrt(i+j)*(int)sqrt(i+j)==i+j){
                adde(i,j+ma,1);
                adde(j+ma,i,0);
            }
        }
    }
    return ma-dinic();
}
int pre[M],nxt[M],n;
bool vis[M];
bool check(int mid){
    if(solve(mid)<=n)return 1;
    return 0;
}
signed main(){
    int now=1;
    cin>>n;
    int l=1,r=MM,mid;
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid))l=mid+1,now=mid;
        else r=mid-1;
        // cout<<l<<' '<<r<<endl;
    }
    if(check(now-1))now++;
    if(!check(now-1))now--;
    cout<<now-1<<endl;
    return 0;
}