easylin0126@gmail.com
(林榮翼)
學校
:
臺北市立成功高級中學
編號 : 89424
來源 : [140.114.207.162]
最後登入時間 ：
2023-09-27 16:33:24
jackyname1@gmail.com
(☆♬○♩程式家小崴●♪✧♩)
學校
:
基隆市私立二信高級中學
編號 : 77382
來源 : [114.32.51.178]
最後登入時間 ：
2022-04-12 19:45:18
想請教演算法相關的問題><，我利用匈牙利演算法求二分圖最大匹配，不過在第三個測試點一直TLE(NA(score:73%))
想請教大大們!!)，題目有提示該測資為連通圖，不過我不曉得怎麼利用這個性質QQ，
#2: 27% TLE (4s)
Killed
是用匈牙利演算法求二分圖最大匹配 沒錯~ !
至於技巧是在 adjacent list 的實作時，用 一個 vector<int> adj[maxn]
然後 a b 相鄰 就 adj[a].push_back(b); adj[b].push_back(a);
匈牙利演算法 搜尋時 就直接用 adj 搜
我的程式至少快了 4 倍!!!
以上，希望有幫到你~~ :)
easylin0126@gmail.com
(林榮翼)
學校
:
臺北市立成功高級中學
編號 : 89424
來源 : [140.114.207.162]
最後登入時間 ：
2023-09-27 16:33:24
想請教演算法相關的問題><，我利用匈牙利演算法求二分圖最大匹配，不過在第三個測試點一直TLE(NA(score:73%))
想請教大大們!!)，題目有提示該測資為連通圖，不過我不曉得怎麼利用這個性質QQ，
#2: 27% TLE (4s)
Killed
是用匈牙利演算法求二分圖最大匹配 沒錯~ !
至於技巧是在 adjacent list 的實作時，用 一個 vector adj[maxn]
然後 a b 相鄰 就 adj[a].push_back(b); adj[b].push_back(a);
匈牙利演算法 搜尋時 就直接用 adj 搜
我的程式至少快了 4 倍!!!
以上，希望有幫到你~~ :)
我也是用這種方式!!不過TLE QQ，我是利用乘2和乘2+1去區別x.y，
#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
int match[200005];
bool used[200005];
vector<int> g[200005];
inline bool DFS(int v){
used[v]=1;
for(auto x:g[v]){
int con=match[x];
if(!con||(!used[con]&&DFS(con))){
match[x]=v;
match[v]=x;
return 1;
}
}
return 0;
}
int main(){
int i,t,x,y,p,q,k;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&p,&q,&k);
memset(match,-1,sizeof(match));
for(i=0;i<k;i++){
scanf("%d%d",&x,&y);
g[x<<1].emplace_back((y<<1)+1);
g[(y<<1)+1].emplace_back(x<<1);
match[x<<1]=match[(y<<1)+1]=0;
}
int limit=max((p<<1),(q<<1)+1),ans=0;
for(i=1;i<=limit;i++){
if(!match[i]){
memset(used,0,sizeof(used));
if(DFS(i))
ans++;
}
}
printf("%d\n",ans);
if(t){
for(i=1;i<=limit;i++)
g[i].clear();
}
}
}