P2765 魔術(shù)球問題

題目描述

?問題描述：

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

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

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

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

?編程任務(wù)：

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

輸入格式

第1 行有1個正整數(shù)n，表示柱子數(shù)。

輸出格式

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

輸入輸出樣例

輸入 #1復(fù)制

4

輸出 #1復(fù)制

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

說明/提示

4<=n<=55

思路：

首先知道放球的個數(shù)和柱子的個數(shù)是成正相關(guān)的，

一直增加球，對于每一個球i，將比其小的，能和其相加為平方數(shù)的，統(tǒng)一連中間邊。

之所以叫中間邊，是因為這題要拆點，設(shè)源點和匯點分別為S和T。

將每一個點i，拆為 Xi，Yi，

每一個點將其S與Xi連接，Yi與T連接，

中間點就是如果i節(jié)點和j節(jié)點相連接，

就Xi 與Yj，相連，。以上講到的邊，流量全為1.

當(dāng)num個數(shù)建立的容量網(wǎng)絡(luò)的最小邊覆蓋x>n時，即n個柱子無法覆蓋掉num個數(shù)時，

結(jié)束加邊操作，此時num-1，就是N個柱子能覆蓋到的最大數(shù)字。

在dinic算法中增光路的過程中，記錄每一個v，增廣的下一個節(jié)節(jié)點u。

一路鏈狀輸出就是方法。

代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define sz(a) int(a.size()) #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl #define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c)) #define du2(a,b) scanf("%d %d",&(a),&(b)) #define du1(a) scanf("%d",&(a)); using namespace std; typedef long long ll; ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} ll powmod(ll a, ll b, ll MOD) {a %= MOD; if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;} void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}} void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}inline void getInt(int* p); const int maxn = 1000010; const int inf = 0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ const int INF = (1 << 30); const int MAXN = 400000; int idx = 0, e[MAXN], f[MAXN], ne[MAXN], h[100000]; void add(int a, int b, int c) {e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx++;e[idx] = a, ne[idx] = h[b], f[idx] = 0, h[b] = idx++; } int S, T, ch[MAXN], q[MAXN], nex[MAXN]; bool tell() {memset(ch, -1, sizeof(ch));int head = 0, tail = 0;ch[q[0] = S] = 0;while (head <= tail) {int t = q[head++];for (int i = h[t]; i != -1; i = ne[i]) {if (ch[e[i]] == -1 && f[i]) {ch[q[++tail] = e[i]] = ch[t] + 1;}}}return ch[T] != -1; } int zeng(int a, int b) {if (a == T)return b;int r = 0;for (int i = h[a]; i != -1; i = ne[i]) {if (ch[a] + 1 == ch[e[i]] && f[i]) {int t = zeng(e[i], min(b - r, f[i]));if (t > 0){// 可找路徑。nex[a >> 1] = (e[i] >> 1);}f[i] -= t; r += t; f[i ^ 1] += t;}}if (!r)ch[a] = -1;return r; } int dinic() {int r = 0, t = 0;while (tell()) {while (t = zeng(S, INF)) {r += t;}}return r; } void set_S_T(int s, int t) {S = s;T = t; } void init() {memset(h, -1, sizeof(h));memset(nex, -1, sizeof(nex)); } int n; int w[1000]; bool vis[maxn]; int main() {//freopen("D:\\code\\text\\input.txt","r",stdin);//freopen("D:\\code\\text\\output.txt","w",stdout);gbtb;init();S = 0;T = 1e4 + 10;cin >> n;int now = 0;int num = 0;while (now <= n){++num;add(S, num << 1, 1);add((num << 1) | 1, T, 1);for (int i = sqrt(num) + 1; i * i < (num << 1); ++i){add((i * i - num) << 1, (num << 1) | 1, 1);}int s = dinic();if (!s){w[++now] = num;}}cout << num - 1 << endl;int k;repd(i, 1, n){if (!vis[w[i]]){k = w[i];cout << k;vis[k] = 1;while (nex[k] != -1 && nex[k] != (T) >> 1 ){k=nex[k];vis[k]=1;cout<<" "<<k;}cout<<endl;}}return 0; }inline void getInt(int* p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}}else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

轉(zhuǎn)載于:https://www.cnblogs.com/qieqiemin/p/11632802.html

總結(jié)

以上是生活随笔為你收集整理的洛谷 P2765 魔术球问题 （dinic求最大流，最小边覆盖）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。