我整个下午都在调整魔芋
以后再来说说这个算法的原理。
理论上，这种做法可以处理一切 问题。
#include<bits/stdc .h> #define inf 0x3f3f3f3f using namespace std; const int N=55*55; //判断是否存在匹配包含 (u,v) ///看是否有环 //如果有环，则取反所有路径 //**然后删掉 (u,v) 这条边** //适用于完美匹配 -> 拆点 建虚点 int n,match[N],dfn[N],l[N],r[N],cnt,num,in[N],id[N]; char ch[55]; vector<int> g[N],g2[N]; //dfn 标记在右节点 bool dfs(int u) {
for(auto v:g2[u]) {
if(dfn[v]==num) continue; dfn[v]=num; if(match[v]==-1||dfs(match[v])) {
match[v]=u;
return 1;
}
}
return 0;
}
int dfs(int u,int topf) {
for(auto v:g2[u]) {
if(dfn[v]==num) continue;
dfn[v]=num;
if(match[v]==topf||(match[v]>topf&&dfs(match[v],topf)!=-1)) {
match[v]=u;
return v;
}
}
return -1;
}
bool check(int mid) {
cnt=0;
for(int i=0;i<n;i++) in[i]=mid;
in[n]=n;
for(int i=0;i<=n;i++) {
l[i]=cnt;
for(int j=1;j<=in[i];j++) {
id[cnt++]=i;
}
r[i]=cnt;
}
for(int i=0;i<n;i++) {
g2[i].clear();
}
for(int i=0;i<n;i++) {
for(auto j:g[i]) {
for(int k=l[j];k<r[j];k++) {
g2[i].push_back(k);
}
}
}
memset(match,-1,sizeof match);
for(int i=0;i<=n-1;i++) {
num++;
if(!dfs(i)) return 0;
}
return 1;
}
int main() {
scanf("%d",&n);
scanf("%s",ch);
for(int i=0;i<n;i++) {
char Ch[55]; scanf("%s",Ch);
for(int j=0;j<n;j++) {
if(Ch[j]=='Y') {
g[i].push_back(j);
}
}
}
for(int i=0;i<n;i++) {
if(ch[i]=='Y') {
g[i].push_back(n);
}
}
int l=0,r=n,res=0;
while(l<=r) {
int mid=(l+r)/2;
if(check(mid)) res=mid,r=mid-1;
else l=mid+1;
}
check(res);
for(int i=n;i<cnt;i++) {
for(int j=0;j<cnt;j++) {
g2[i].push_back(j);
}
dfs(i);
}
for(int i=0;i<n;i++) {
num++;
printf("%d ",id[dfs(i,i)]);
}
}