hdu 1281 棋盘游戏网络流

http://acm.hdu.edu.cn/showproblem.php?pid=1281

题意：小希和Gardon在玩一个游戏：对一个N*M的棋盘，在格子里放尽量多的一些国际象棋里面的“车”，并且使得他们不能互相攻击，这当然很简单，但是Gardon限制了只有某些格子才可以放，小希还是很轻松的解决了这个问题（见下图）注意不能放车的地方不影响车的互相攻击。
所以现在Gardon想让小希来解决一个更难的问题，在保证尽量多的“车”的前提下，棋盘里有些格子是可以避开的，也就是说，不在这些格子上放车，也可以保证尽量多的“车”被放下。但是某些格子若不放子，就无法保证放尽量多的“车”，这样的格子被称做重要点。Gardon想让小希算出有多少个这样的重要点，你能解决这个问题么？
题解：二分图最大匹配。跑最大流.要使每行每列最多一个车。熟悉二分匹配的人肯定就会想到：把x，y分别当作二分图的两一个部分，最大匹配就是要求的最多的车的数量。这样的原因也很好理解。最大匹配中，每个x点，y点最多只有一条边链接（不包含链接源点和汇点），也就是说，去相同的x或者y,最多只有一个点。要问哪些车是不能没有的，只需要枚举每一个车，如果去掉这个车，最大匹配减小，就是所求的重要点。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define inf (1<<29)
const int maxn = 1000 , maxm = 100000;
int NV,n,m,k;
int gap[maxn],dis[maxn],pre[maxn],cur[maxn];
struct Edge {
    int v,f,next;
    Edge() {}
    Edge( int _v,int _f,int _next ) : v(_v),f(_f),next(_next){}    
}edge[maxm];
int E,head[maxn];
void init() {
    E=0;
    memset(head,-1,sizeof(head));    
}
void addedge(int u,int v,int f) {
    edge[E]=Edge(v,f,head[u]);
    head[u]=E++;
    edge[E]=Edge(u,0,head[v]);
    head[v]=E++;    
}
int sap(int st , int en) {
    int maxf = 0;
    for(int i=0;i<NV;i++) {
        dis[i] = gap[i] = 0;
        cur[i] = head[i];    
    }    
    int u = pre[st] = st;
    int aug = inf;
    gap[0] = NV;
    while(dis[st] < NV) {
loop:   for(int &i=cur[u];i!=-1;i=edge[i].next) {
            int v = edge[i].v;
            if(edge[i].f && dis[u]==dis[v]+1) {
                aug = aug < edge[i].f?aug:edge[i].f;
                pre[v] = u;
                u = v;
                if(v == en) {
                    maxf += aug;
                    for(u=pre[u];v!=st;v=u,u=pre[u]) {
                        edge[cur[u]].f -= aug;
                        edge[cur[u]^1].f += aug;    
                    }    
                    aug = inf;
                }    
                goto loop;
            }
        }   
        int mindis = NV;
        for(int i=head[u];i!=-1;i=edge[i].next) {
            int v=edge[i].v;
            if(edge[i].f && mindis > dis[v]) {
                cur[u] = i;
                mindis = dis[v];    
            }  
        }
        if( --gap[dis[u]] == 0 ) break;
        gap[ dis[u] = mindis + 1 ] ++;
        u = pre[u];
    }
    return maxf;
}
pair<int,int> kp[10005];
void Build_Graph( int id ) {
    int st = 0;
    int en = n + m + 1;
    init();
    for( int i = 1 ; i <= n ; i++ )
        addedge(st,i,1);
    for( int j = 1 ; j <= m ; j++ )
        addedge(j+n,en,1);
    for( int i = 0 ; i < k ; i++ ) {
        if( i == id ) continue;
        addedge(kp[i].first,kp[i].second+n,1);
    }
}
int main() {
    int cas = 0;
    while( scanf("%d%d%d",&n,&m,&k) != EOF ) {
        int st = 0;
        int en = n + m + 1;
        NV = n+m+2;
        init();
        int a,b;
        for( int i = 0 ; i < k ; i++ ) {
            scanf("%d%d",&kp[i].first,&kp[i].second);
            addedge(kp[i].first,kp[i].second+n,1);
        }
        for( int i = 1 ; i <= n ; i++ )
            addedge(st,i,1);
        for( int j = 1 ; j <= m ; j++ )
            addedge(j+n,en,1);
        int maxflow = sap(st,en);
        int cnt = 0;
        for( int i = 0 ; i < k ; i++ ) {
            Build_Graph(i);
            int cmp = sap(st,en);
            if( cmp != maxflow ) cnt++;
        }
        printf("Board %d have %d important blanks for %d chessmen.\n",++cas,cnt,maxflow);
    }
    return 0;
}

优质内容筛选与推荐>>
1、密度聚类 - DBSCAN算法
2、影响35岁前成功的好习惯与坏习惯
3、使用Playground编写第一个Swift程序
4、markdown翻译
5、设计模式学习心得20180903

0 │ 收藏 │ 举报

朋友将在看一看看到

分享想法到看一看