BZOJ 1458: 士兵占领

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
题解
代码

Description

有一个M * N的棋盘，有的格子是障碍。现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘当满足第i行至少放置了Li个士兵, 第j列至少放置了Cj个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。

Input

第一行两个数M, N, K分别表示棋盘的行数，列数以及障碍的个数。第二行有M个数表示Li。第三行有N个数表示Ci。接下来有K行，每行两个数X, Y表示(X, Y)这个格子是障碍。

Output

输出一个数表示最少需要使用的士兵个数。如果无论放置多少个士兵都没有办法占领整个棋盘，输出”JIONG!” (不含引号)

Sample Input

4 4 4
1 1 1 1
0 1 0 3
1 4
2 2
3 3
4 3

Sample Output

4
数据范围
M, N <= 100, 0 <= K <= M * N

题解

这道题目感觉建图是有一点点脑洞的！
首先判断全放置了能不能满足要求！如果能的话，就进行网络流！
首先我们考虑每一行和每一列能删的最多的格子数，从源连到每一行，流量为每一行能删的格子数，再从每一列连到汇，流量为每一列能删掉的格子数量。这样一点一行一列都有可以删的格子，那么删掉好了！所以我们把没有禁止的格子的行和列再相连，流量为1，跑一边最大流，得出能删的最多的格子数。
用全部能放的格子数减去就是结果。

代码

/*Author:WNJXYK*/
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int Maxt=200;
int limitLine[Maxt+5],limitRow[Maxt+5];
int judgeLine[Maxt+5],judgeRow[Maxt+5];
int n,m,k;
bool map[Maxt+5][Maxt+5];
inline int remin(int a,int b){return a<b?a:b;}
const int Maxn=200;
const int Maxm=20000;
const int inf=2147483647;
struct Edge{
    int u,v,f,nxt;
    Edge(){}
    Edge(int a,int b,int c,int d){
        u=a;
        v=b;
        f=c;
        nxt=d;
    }
};
Edge e[Maxm+10];
int g[Maxn+10];
int cnt=1;
int sink,src;
inline void insertEdge(int u,int v,int f){
    cnt++;
    e[cnt]=Edge(u,v,f,g[u]);
    g[u]=cnt;
}
inline void addEdge(int u,int v,int f){
    insertEdge(u,v,f);
    insertEdge(v,u,0);
}
queue<int> que;
int dist[Maxn+10];
bool spfa(){
    while(!que.empty()) que.pop();
    memset(dist,-1,sizeof(dist));
    dist[src]=0;
    que.push(src);
    while(!que.empty()){
        int now=que.front();
        que.pop();
        for (int i=g[now];i;i=e[i].nxt){
            if (e[i].f!=0 && dist[e[i].v]==-1){
                dist[e[i].v]=dist[now]+1;
                que.push(e[i].v);
            }
        }
    }
    return dist[sink]!=-1;
}
int dfs(int x,int delta){
    int ret=0;
    if (x==sink){
        return delta;
    }else{
        for (int i=g[x];i;i=e[i].nxt){
            if (e[i].f!=0 && dist[e[i].v]==dist[x]+1){
                int ddelta=dfs(e[i].v,remin(e[i].f,delta));
                e[i].f-=ddelta;
                e[i^1].f+=ddelta;
                ret+=ddelta;
                delta-=ddelta;
            }
        }
    }
    return ret;
}
int dinic(){
    int ret=0;
    while(spfa()){
        ret+=dfs(src,inf);
    }
    return ret;
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=n;i++) {
        judgeRow[i]=m;
        scanf("%d",&limitRow[i]);
    }
    for (int i=1;i<=m;i++){
        judgeLine[i]=n;
        scanf("%d",&limitLine[i]);
    }
    int sum=n*m;
    for (int i=1;i<=k;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        if (!map[x][y]){
            map[x][y]=true;judgeRow[x]--;judgeLine[y]--;
            sum--;
        }
    }
    bool isJoing=false;
    for (int i=1;i<=n&&!isJoing;i++)isJoing&=(judgeRow[i]>=limitRow[i]);
    for (int i=1;i<=m&&!isJoing;i++)isJoing&=(judgeLine[i]>=limitLine[i]);
    if (isJoing){
        printf("JIONG!n");
        return 0;
    }
    src=m+n+1;sink=m+n+2;
    for (int i=1;i<=n;i++) addEdge(src,i,judgeRow[i]-limitRow[i]);
    for (int j=1;j<=m;j++) addEdge(n+j,sink,judgeLine[j]-limitLine[j]);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (!map[i][j]) addEdge(i,n+j,1);
        }
    }
    printf("%dn",sum-dinic());
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

/*Author:WNJXYK*/

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

const int Maxt=200;

int limitLine[Maxt+5],limitRow[Maxt+5];

int judgeLine[Maxt+5],judgeRow[Maxt+5];

int n,m,k;

bool map[Maxt+5][Maxt+5];

inline int remin(int a,int b){return a<b?a:b;}

const int Maxn=200;

const int Maxm=20000;

const int inf=2147483647;

struct Edge{

int u,v,f,nxt;

Edge(){}

Edge(int a,int b,int c,int d){

u=a;

v=b;

f=c;

nxt=d;

}

};

Edge e[Maxm+10];

int g[Maxn+10];

int cnt=1;

int sink,src;

inline void insertEdge(int u,int v,int f){

cnt++;

e[cnt]=Edge(u,v,f,g[u]);

g[u]=cnt;

}

inline void addEdge(int u,int v,int f){

insertEdge(u,v,f);

insertEdge(v,u,0);

}

queue<int> que;

int dist[Maxn+10];

bool spfa(){

while(!que.empty()) que.pop();

memset(dist,-1,sizeof(dist));

dist[src]=0;

que.push(src);

while(!que.empty()){

int now=que.front();

que.pop();

for (int i=g[now];i;i=e[i].nxt){

if (e[i].f!=0 && dist[e[i].v]==-1){

dist[e[i].v]=dist[now]+1;

que.push(e[i].v);

}

return dist[sink]!=-1;

}

int dfs(int x,int delta){

int ret=0;

if (x==sink){

return delta;

}else{

for (int i=g[x];i;i=e[i].nxt){

if (e[i].f!=0 && dist[e[i].v]==dist[x]+1){

int ddelta=dfs(e[i].v,remin(e[i].f,delta));

e[i].f-=ddelta;

e[i^1].f+=ddelta;

ret+=ddelta;

delta-=ddelta;

}

return ret;

}

int dinic(){

int ret=0;

while(spfa()){

ret+=dfs(src,inf);

}

return ret;

}

int main(){

scanf("%d%d%d",&n,&m,&k);

for (int i=1;i<=n;i++) {

judgeRow[i]=m;

scanf("%d",&limitRow[i]);

}

for (int i=1;i<=m;i++){

judgeLine[i]=n;

scanf("%d",&limitLine[i]);

}

int sum=n*m;

for (int i=1;i<=k;i++) {

int x,y;

scanf("%d%d",&x,&y);

if (!map[x][y]){

map[x][y]=true;judgeRow[x]--;judgeLine[y]--;

sum--;

}

bool isJoing=false;

for (int i=1;i<=n&&!isJoing;i++)isJoing&=(judgeRow[i]>=limitRow[i]);

for (int i=1;i<=m&&!isJoing;i++)isJoing&=(judgeLine[i]>=limitLine[i]);

if (isJoing){

printf("JIONG!n");

return 0;

}

src=m+n+1;sink=m+n+2;

for (int i=1;i<=n;i++) addEdge(src,i,judgeRow[i]-limitRow[i]);

for (int j=1;j<=m;j++) addEdge(n+j,sink,judgeLine[j]-limitLine[j]);

for (int i=1;i<=n;i++){

for (int j=1;j<=m;j++){

if (!map[i][j]) addEdge(i,n+j,1);

}

printf("%dn",sum-dinic());

return 0;

}

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

WNJXYKの博客

喂你脚下有坑