魔術球問題

時空限制1000ms / 128MB

題目描述

?問題描述：

假設有n根柱子，現要按下述規則在這n根柱子中依次放入編號為1，2，3，...的球。

（1）每次只能在某根柱子的最上面放球。

（2）在同一根柱子中，任何2個相鄰球的編號之和為完全平方數。

試設計一個算法，計算出在n根柱子上最多能放多少個球。例如，在4 根柱子上最多可放11 個球。

?編程任務：

對于給定的n，計算在n根柱子上最多能放多少個球。

輸入輸出格式

輸入格式：

?

第1 行有1個正整數n，表示柱子數。

?

輸出格式：

?

程序運行結束時，將n 根柱子上最多能放的球數以及相應的放置方案輸出。文件的第一行是球數。接下來的n行，每行是一根柱子上的球的編號。

?

輸入輸出樣例

輸入樣例：?
4 輸出樣例：?
11 1 8 2 7 9 3 6 10 4 5 11

說明

4<=n<=55

---

最小路徑覆蓋問題。

DAG的最小路徑覆蓋：

定義：在一個有向圖中，找出最少的路徑，使得這些路徑經過了所有的點，且這些路徑之間不會經過相同的點。

算法：把原圖的每個點V拆成Vx和Vy兩個點，如果有一條有向邊A->B，那么就加邊Ax?>By。這樣就得到了一個二分圖。那么最小路徑覆蓋=原圖的結點數-新圖的最大匹配數。

?

證明：一開始每個點都是獨立的為一條路徑，總共有n條不相交路徑。我們每次在二分圖里找一條匹配邊就相當于把兩條路徑合成了一條路徑，也就相當于路徑數減少了1。所以找到了幾條匹配邊，路徑數就減少了多少。所以有最小路徑覆蓋=原圖的結點數-新圖的最大匹配數。因為路徑之間不能有公共點，所以加的邊之間也不能有公共點，這就是匹配的定義。

?

再回來看本題，若兩個球編號之和是完全平方數則連邊，這樣最小路徑覆蓋數就是柱子數。但是題目給你的是柱子數，要求球數，可以二分球數判斷最少需要多少個柱子。

本題的另一個難點是輸出每根柱子上球的編號，就是輸出最小路徑覆蓋路徑集合的每一條路徑上的點。考慮我們是如何求最小路徑覆蓋的，我們一開始認為路徑集合就是點集，然后找到一個匹配邊，把這個邊的兩個點所在的集合合并成一個集合（其實就是把兩條路徑合并成一條路徑）。因為我的最大匹配是用最大流寫的，所以最后我判斷某兩個點是否在一條路徑上，就直接判斷它們的反向邊是否有流量（注意這里的兩個點并不是任意的兩個點，而是一條路徑上相鄰的兩個點）。

#include<bits/stdc++.h> #define N 3250 using namespace std;typedef struct {int v;long long flow; }ss; ss edg[N*N]; vector<int>edges[N]; int now_edges=0; int fl[N][N];void init() {for(int i=0;i<N;i++)edges[i].clear();now_edges=0; }void addedge(int u,int v,long long flow) {fl[u][v]+=flow;edges[u].push_back(now_edges);edg[now_edges++]=(ss){v,flow};edges[v].push_back(now_edges);edg[now_edges++]=(ss){u,0}; }int dis[N],S,T;bool bfs() {queue<int>q;q.push(S);memset(dis,0,sizeof(dis));dis[S]=1;while(!q.empty()){int now=q.front();q.pop();int Size=edges[now].size();for(int i=0;i<Size;i++){ss e=edg[edges[now][i]];if(e.flow>0&&dis[e.v]==0){dis[e.v]=dis[now]+1;q.push(e.v);}}}if(dis[T]==0)return 0;return 1; }int current[N];long long dfs(int now,long long maxflow) {if(now==T)return maxflow;int Size=edges[now].size();for(int i=current[now];i<Size;i++){current[now]=i;ss &e=edg[edges[now][i]];if(e.flow>0&&dis[e.v]==dis[now]+1){long long Flow=dfs(e.v,min(maxflow,e.flow));if(Flow!=0){fl[now][e.v]-=Flow;fl[e.v][now]+=Flow;e.flow-=Flow;edg[edges[now][i]^1].flow+=Flow;return Flow;}}}return 0; }long long dinic() {long long ans=0,flow;while(bfs()){memset(current,0,sizeof(current));while(flow=dfs(S,LLONG_MAX/2))ans+=flow;}return ans; }int f(int n) //返回球數是n的時候的最小路徑覆蓋數 {init();S=2*n+1;T=2*n+2;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++)if((int)sqrt(i+j)*(int)sqrt(i+j)==(i+j))addedge(2*i-1,2*j,1); addedge(S,2*i-1,1);addedge(2*i,T,1);}return n-dinic(); }int vis[N]={0};void ff(int x,int ans) //dfs尋找每條路徑上的點，由于題目的特殊性可以從小到大按順序尋找 {printf("%d ",x);vis[x]=1;for(int i=x+1;i<=ans;i++)if(fl[i*2][x*2-1]){ff(i,ans);break;} }int main() {int n;scanf("%d",&n);int Left=1,Right=1600,ans=1;while(Left<=Right){int mid=(Left+Right)/2;if(f(mid)<=n){ans=mid;Left=mid+1;}else Right=mid-1;}printf("%d\n",ans);for(int i=1;i<=ans;i++){if(!vis[i])ff(i,ans),printf("\n");;}return 0; } View Code

?

?

轉載于:https://www.cnblogs.com/tian-luo/p/9521408.html

總結

以上是生活随笔為你收集整理的网络流24题-魔术球问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。