BZOJ4950: [Wf2017]Mission Improbable【二分图匹配】

4950: [Wf2017]Mission Improbable

【题目描述】

传送门

【题解】

对于每行每列只需要考虑最高的就可以了。
减去每行每列的最大值,还要加上重复减掉的值,行列最大值都一样的时候,就多剪了,所以就加回去。

代码如下

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,tim,grl[105],a[105][105],H[105],L[105],vis[105];long long Ans;
struct xcw{
    int tot,lnk[105],son[10005],nxt[10005];
    void Add(int x,int y){son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
}E;
bool Fnd(int x){
    for(int j=E.lnk[x];j;j=E.nxt[j])
    if(vis[E.son[j]]!=tim){
        vis[E.son[j]]=tim;
        if(!grl[E.son[j]]||Fnd(grl[E.son[j]])){grl[E.son[j]]=x;return 1;}
    }
    return 0;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) scanf("%d",&a[i][j]),H[i]=max(H[i],a[i][j]),L[j]=max(L[j],a[i][j]),Ans+=max(a[i][j]-1,0);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) if(a[i][j]&&H[i]==L[j]&&H[i]) E.Add(i,j);
    for(int i=1;i<=n;i++) Ans-=max(H[i]-1,0);
    for(int j=1;j<=m;j++) Ans-=max(L[j]-1,0);
//  for(int i=1;i<=n;i++) ++tim,Fnd(i);
//  for(int i=1;i<=m;i++) if(grl[i]) Ans+=max(L[i]-1,0);
    for(int i=1;i<=n;i++){
        ++tim;
        if(Fnd(i)) Ans+=max(H[i]-1,0);
    }
    printf("%lld\n",Ans);
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部