首页 > 代码库 > BZOJ1458: 士兵占领
BZOJ1458: 士兵占领
题解：
裸上下界网络流。。。就当复习了。。。这个资料不错：http://hi.baidu.com/newfarking/item/b9780317201c9651f0090e64
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 500+5 14 #define maxm 100000 15 #define eps 1e-10 16 #define ll long long 17 #define pa pair<int,int> 18 #define for0(i,n) for(int i=0;i<=(n);i++) 19 #define for1(i,n) for(int i=1;i<=(n);i++) 20 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 21 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 22 #define for4(i,x) for(int i=head[x],y;i;i=e[i].next) 23 #define mod 1000000007 24 using namespace std; 25 inline int read() 26 { 27 int x=0,f=1;char ch=getchar(); 28 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 29 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 30 return x*f; 31 } 32 int n,m,s,t,ss,tt,tot=1,cnt,c[maxm],head[maxn],cur[maxn],h[maxn],a[maxn]; 33 queue<int>q; 34 bool b[maxn][maxn]; 35 struct edge{int go,next,v;}e[maxm]; 36 inline void ins(int x,int y,int w) 37 { 38 e[++tot]=(edge){y,head[x],w};head[x]=tot; 39 e[++tot]=(edge){x,head[y],0};head[y]=tot; 40 } 41 inline void insert(int x,int y,int l,int r) 42 { 43 ins(ss,y,l);c[++cnt]=tot-1; 44 ins(x,tt,l);c[++cnt]=tot-1; 45 ins(x,y,r-l); 46 } 47 bool bfs() 48 { 49 for(int i=0;i<=n+m+3;i++)h[i]=-1; 50 q.push(s);h[s]=0; 51 while(!q.empty()) 52 { 53 int x=q.front();q.pop(); 54 for(int i=head[x];i;i=e[i].next) 55 if(e[i].v&&h[e[i].go]==-1) 56 { 57 h[e[i].go]=h[x]+1;q.push(e[i].go); 58 } 59 } 60 return h[t]!=-1; 61 } 62 int dfs(int x,int f) 63 { 64 if(x==t) return f; 65 int tmp,used=0; 66 for(int i=cur[x];i;i=e[i].next) 67 if(e[i].v&&h[e[i].go]==h[x]+1) 68 { 69 tmp=dfs(e[i].go,min(e[i].v,f-used)); 70 e[i].v-=tmp;if(e[i].v)cur[x]=i; 71 e[i^1].v+=tmp;used+=tmp; 72 if(used==f)return f; 73 } 74 if(!used) h[x]=-1; 75 return used; 76 } 77 int dinic() 78 { 79 int maxflow=0; 80 while(bfs()) 81 { 82 for (int i=0;i<=n+m+3;i++)cur[i]=head[i];maxflow+=dfs(s,inf); 83 } 84 return maxflow; 85 } 86 87 int minflow() 88 { 89 s=ss;t=tt; 90 dinic(); 91 for1(i,cnt)if(e[c[i]].v){printf("JIONG!\n");return 0;} 92 int ans=e[tot].v; 93 e[tot].v=e[tot^1].v=0; 94 s=n+m+1;t=0; 95 return ans-dinic(); 96 } 97 int main() 98 { 99 freopen("input.txt","r",stdin);100 freopen("output.txt","w",stdout);101 n=read();m=read();int k=read();102 s=0;t=n+m+1;ss=t+1;tt=t+2;103 for1(i,n+m)a[i]=read();104 for1(i,k){int x=read(),y=read();b[x][y]=1;}105 for1(i,n)for1(j,m)if(!b[i][j])insert(i,j+n,0,1);106 for1(i,n)insert(s,i,a[i],inf);107 for2(i,n+1,n+m)insert(i,t,a[i],inf);108 insert(t,s,0,inf);109 printf("%d\n",minflow());110 return 0;111 }
UPD：想起可以这样判可行流
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 500+5 14 #define maxm 100000 15 #define eps 1e-10 16 #define ll long long 17 #define pa pair<int,int> 18 #define for0(i,n) for(int i=0;i<=(n);i++) 19 #define for1(i,n) for(int i=1;i<=(n);i++) 20 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 21 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 22 #define for4(i,x) for(int i=head[x],y;i;i=e[i].next) 23 #define mod 1000000007 24 using namespace std; 25 inline int read() 26 { 27 int x=0,f=1;char ch=getchar(); 28 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 29 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 30 return x*f; 31 } 32 int n,m,s,t,ss,tt,tot=1,cnt,head[maxn],cur[maxn],h[maxn],a[maxn]; 33 queue<int>q; 34 bool b[maxn][maxn]; 35 struct edge{int go,next,v;}e[maxm]; 36 inline void ins(int x,int y,int w) 37 { 38 e[++tot]=(edge){y,head[x],w};head[x]=tot; 39 e[++tot]=(edge){x,head[y],0};head[y]=tot; 40 } 41 inline void insert(int x,int y,int l,int r) 42 { 43 cnt+=l; 44 ins(ss,y,l); 45 ins(x,tt,l); 46 ins(x,y,r-l); 47 } 48 bool bfs() 49 { 50 for(int i=0;i<=n+m+3;i++)h[i]=-1; 51 q.push(s);h[s]=0; 52 while(!q.empty()) 53 { 54 int x=q.front();q.pop(); 55 for(int i=head[x];i;i=e[i].next) 56 if(e[i].v&&h[e[i].go]==-1) 57 { 58 h[e[i].go]=h[x]+1;q.push(e[i].go); 59 } 60 } 61 return h[t]!=-1; 62 } 63 int dfs(int x,int f) 64 { 65 if(x==t) return f; 66 int tmp,used=0; 67 for(int i=cur[x];i;i=e[i].next) 68 if(e[i].v&&h[e[i].go]==h[x]+1) 69 { 70 tmp=dfs(e[i].go,min(e[i].v,f-used)); 71 e[i].v-=tmp;if(e[i].v)cur[x]=i; 72 e[i^1].v+=tmp;used+=tmp; 73 if(used==f)return f; 74 } 75 if(!used) h[x]=-1; 76 return used; 77 } 78 int dinic() 79 { 80 int maxflow=0; 81 while(bfs()) 82 { 83 for (int i=0;i<=n+m+3;i++)cur[i]=head[i];maxflow+=dfs(s,inf); 84 } 85 return maxflow; 86 } 87 88 int minflow() 89 { 90 s=ss;t=tt; 91 if(dinic()!=cnt){printf("JIONG\n");return 0;} 92 int ans=e[tot].v; 93 e[tot].v=e[tot^1].v=0; 94 s=n+m+1;t=0; 95 return ans-dinic(); 96 } 97 int main() 98 { 99 freopen("input.txt","r",stdin);100 freopen("output.txt","w",stdout);101 n=read();m=read();int k=read();102 s=0;t=n+m+1;ss=t+1;tt=t+2;103 for1(i,n+m)a[i]=read();104 for1(i,k){int x=read(),y=read();b[x][y]=1;}105 for1(i,n)for1(j,m)if(!b[i][j])insert(i,j+n,0,1);106 for1(i,n)insert(s,i,a[i],inf);107 for2(i,n+1,n+m)insert(i,t,a[i],inf);108 insert(t,s,0,inf);109 printf("%d\n",minflow());110 return 0;111 }
1458: 士兵占领
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 569 Solved: 325
[Submit][Status]
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
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
数据范围
M, N <= 100, 0 <= K <= M * N
BZOJ1458: 士兵占领
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。