我今天早上在刷題的時候發現了我的程式中我一直無法解決的bug。
當我們把DFS
這段代碼中的g[u][v]=0刪去后顯示溢位
然后我想為什么溢位，在哪里溢位的
結果發現在輸入里溢位的，因為那個輸入后面的那個“HAHAHA”都還沒來得及輸出，這時候dfs函式都還沒有被參考。
十分的神奇。
我這里的解決的是最大二分匹配問題，用的是匈牙利演算法。
附原始碼
#include <bits/stdc++.h>
#define DEBUG puts("Here is a BUG")
#define PI 3.1415926535897932626
#define all(a) a.begin(),a.end()
typedef long long ll;
using namespace std;
const double eps=1e-8;
const int MAXN=110;
const int MOD=(int)1e9+7;
const int INF=0x3f3f3f3f;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
int uN,vN,k;
int g[MAXN][MAXN];
int val[MAXN];
int c[MAXN];
int linker[MAXN];
bool used[MAXN];
bool co[MAXN];
bool dfs(int u,int color)
{
for (int v = 0; v < vN; v++)
{
if (g[u][v]==color&&!used[v])
{
g[u][v]=0;
if(linker[v]==-1||dfs(linker[v],color))
{
used[v]=true;
linker[v]=u;
return true;
}
}
}
return false;
}
int solve(int color)
{
int res=0;
memset(linker,-1,sizeof(linker));
for (int u = 0; u < uN; u++)
{
memset(used,false,sizeof(used));
if(dfs(u,color))res++;
}
return res;
}
bool cmp(int a,int b)
{
return val[a]<val[b];
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
while (cin>>vN>>k&&(vN+k))
{
uN=vN;
memset(co,false,sizeof(co));
memset(g,0,sizeof(g));
for (int i = 0; i < vN; i++)
for (int j = 0; j < vN; j++)
{
// cout << "DEBUG i=" << i << " j=" << j << " g[i][j]" << g[i][j] << endl;
cin >> g[i][j];
co[g[i][j]] = true;
// cout << "DEBUG i=" << i << " j=" << j << " g[i][j]" << g[i][j] << endl;
}
puts("HAHAHA");
for (int i = 1; i <= 50; i++)
{
c[i]=i;
if(co[i])val[i]=solve(i);else val[i]=0;
}
sort(c+1,c+51,cmp);
for (int i = 1; i <= 50; i++)
{
k-=val[c[i]];
if(k<0)break;
co[c[i]]=0;
}
vector<int> ans;
for (int i = 1; i <= 50; i++)
{
if(co[i])ans.push_back(i);
}
if (ans.empty())
{
cout<<-1<<endl;
}else{
cout<<ans[0];
for (int i = 1; i < ans.size(); i++)
{
cout<<" "<<ans[i];
}
cout<<endl;
}
}
return 0;
}
附資料
2 1
1 1
1 2
0 0
uj5u.com熱心網友回復：
這個dfs沒有看的明白在進入下一個環節之前， 不是要對當前的這個狀態做標記， 回傳之后清理標記的嗎
沒看明白這個標記的程序，怎么避免重復進入的， 如果能重復進， 堆疊最后就會溢位
g[u][v]=0， 不是做標記嗎？
uj5u.com熱心網友回復：
對我也考慮過了，所以我做了中間輸出的測驗，發現堆疊溢位不是在DFS而是在輸入的時候，這我就搞不明白了，而且已經使用過的點做了used的標記所以最多的dfs的次數也只是n不會溢位
uj5u.com熱心網友回復：
我估計你這個問題不是堆溢位，而是堆疊溢位因為是遞回呼叫，嵌套呼叫dfs
當linker[v]==u的情況下，就是無限遞回呼叫dfs(linker[v],color)
導致堆疊空間耗盡
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/143544.html
標籤：C++ 語言
上一篇：物件 封裝 final 構造方法 多載 static
下一篇：大佬們求教 C語言的