发表文章

[最新] D - 棋盘游戏 二分图-关键点

BePosit 1月前 0

  • 将一个n*m的二维矩阵初始化为0,当哪些位置能够放棋子赋值为1;因为“车”如果在同行或同列会相互攻击,即不能在已有“车”的同行或同列放棋子。直接利用二分匹配求出最多的放旗子数,每次再轮流去掉一个能放棋子的格子,再利用二分匹配查找能放的最多棋子数,若最多棋子数减少,重要格子数加1.
    
    #include<bits/stdc++.h>
    using namespace std;
    #define maxn 105
    bool mmp[maxn][maxn],vis[maxn];
    int n,m,k,match[maxn],u,v,ans,sum,temp;
    bool bfs(int x)
    {
        for(int i=1; i<=m; i++)
        {
            if(mmp[x][i]&&!vis[i])
            {
                vis[i]=1;
                if(match[i]==0||bfs(match[i]))
                {
                    match[i]=x;
                    return true;
                }
            }
        }
        return false ;
    }
    void deal()
    {
        sum=0;
        memset(match,0,sizeof(match));
        for(int i=1; i<=n; i++)
        {
            memset(vis,0,sizeof(vis));
            if(bfs(i))
                sum++;
        }
    }
    int main()
    {
        int top=1;
        while(cin>>n>>m>>k)
        {
            ans=sum=0;
            memset(mmp,0,sizeof(mmp));
            while(k--)
            {
                cin>>u>>v;
                mmp[u][v]=1;
            }
            deal();
            temp=sum;
            for(int i=1; i<=n; i++)
                for(int j=1; j<=m; j++)
                    if(mmp[i][j]==1)
                    {
                        mmp[i][j]=0;
                        deal();
                        if(sum<temp)
                            ans++;
                        mmp[i][j]=1;
                    }
            cout<<"Board "<<top++<<" have "<<ans<<" important blanks for "<<temp<<" chessmen."<<endl;
        }
        return 0;
    }
相关推荐
最新评论 (0)
返回
发表文章
BePosit
文章数
209
评论数
0
注册排名
968402