Gems

zoj2332:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2332

题意:这一道题的题意,我看了很久,也没有看明白,最终还是理解错了。题目的意思是有n*m种石头,有n种形状,m种颜色。一个人对于每一种形状有一定的容忍度,另外一个人对于每一种颜色有一定容忍度,然后问你能把这些石头分给这两个人,使得每个人能够满意。

题解:每一种石头作为一个点,与源点连边,边的容量就是石头的数量,然后每一行作为一个点,对应每一种形状的,容量是INF,然后是每一列一个点,与宝石连接,INF,然后每个行与BF连接,就是每一种形状的容忍度,每一列与GF连接,就是每一种颜色的容忍度,然后BF,GF与汇点连接,INF。

  1 #include<iostream>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<cstdio>
  5 #include<queue>
  6 #define INF 100000000
  7 using namespace std;
  8 const int N=1205;
  9 const int M=1000000;
 10 struct Node{
 11    int v;
 12    int f;
 13    int next;
 14 }edge[M];
 15 int n,m,u,v,cnt,sx,ex;
 16 int head[N],pre[N];
 17 int mp[N][N],a1[N],a2[N];
 18 void init(){
 19     cnt=0;
 20     memset(head,-1,sizeof(head));
 21 }
 22 void add(int u,int v,int w){
 23     edge[cnt].v=v;
 24     edge[cnt].f=w;
 25     edge[cnt].next=head[u];
 26     head[u]=cnt++;
 27     edge[cnt].f=0;
 28     edge[cnt].v=u;
 29     edge[cnt].next=head[v];
 30     head[v]=cnt++;
 31 }
 32 bool BFS(){
 33   memset(pre,0,sizeof(pre));
 34   pre[sx]=1;
 35   queue<int>Q;
 36   Q.push(sx);
 37  while(!Q.empty()){
 38      int d=Q.front();
 39      Q.pop();
 40      for(int i=head[d];i!=-1;i=edge[i].next    ){
 41         if(edge[i].f&&!pre[edge[i].v]){
 42             pre[edge[i].v]=pre[d]+1;
 43             Q.push(edge[i].v);
 44         }
 45      }
 46   }
 47  return pre[ex]>0;
 48 }
 49 int dinic(int flow,int ps){
 50     int f=flow;
 51      if(ps==ex)return f;
 52      for(int i=head[ps];i!=-1;i=edge[i].next){
 53         if(edge[i].f&&pre[edge[i].v]==pre[ps]+1){
 54             int a=edge[i].f;
 55             int t=dinic(min(a,flow),edge[i].v);
 56               edge[i].f-=t;
 57               edge[i^1].f+=t;
 58               flow-=t;
 59              if(flow<=0)break;
 60         }
 61
 62      }
 63       if(f-flow<=0)pre[ps]=-1;
 64       return f-flow;
 65 }
 66 int solve(){
 67     int sum=0;
 68     while(BFS())
 69         sum+=dinic(INF,sx);
 70     return sum;
 71 }
 72 int main() {
 73     int T,k,temp,sum,d,t1,t2,t3,t4,tt=1;
 74     scanf("%d",&T);
 75     while(T--) {
 76          scanf("%d%d",&n,&m);
 77          init();sum=0;
 78         for(int i=1;i<=n;i++)
 79         for(int j=1;j<=m;j++){
 80             scanf("%d",&temp);
 81             sum+=temp;
 82             add(0,(i-1)*m+j,temp);
 83         }
 84
 85         scanf("%d",&d);
 86         for(int i=1;i<=d;i++){
 87             scanf("%d%d%d%d",&t1,&t2,&t3,&t4);
 88             t2++;t4++;
 89             add(t1*m+t2,t3*m+t4,INF);
 90             add(t3*m+t4,t1*m+t2,INF);
 91         }
 92         for(int i=1;i<=n;i++){
 93             scanf("%d",&temp);
 94             for(int j=1;j<=m;j++){
 95                 add((i-1)*m+j,n*m+i,INF);
 96             }
 97             add(n*m+i,n*m+m+n+1,temp);
 98         }
 99         for(int i=1;i<=m;i++){
100             scanf("%d",&temp);
101             for(int j=1;j<=n;j++){
102             add((j-1)*m+i,n*m+n+i,INF);
103             }
104             add(n*m+n+i,n*m+m+n+2,temp);
105         }
106         add(n*m+n+m+1,n*m+n+m+3,INF);
107         add(n*m+n+m+2,n*m+n+m+3,INF);
108         sx=0,ex=n*m+n+m+3;
109         int td=solve();
110         if(td==sum)printf("Yes\n");
111         else
112             printf("No\n");
113     }
114     return 0;
115 }

时间: 09-01

Gems的相关文章

(状压dp)HDU 4778 Gems Fight!

Gems Fight! Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 327680/327680 K (Java/Others)Total Submission(s): 2395    Accepted Submission(s): 1087 Problem Description Alice and Bob are playing "Gems Fight!": There are Gems of G differe

cocoapods无法使用淘宝镜像,使用https://gems.ruby-china.org/方法

1.将gem sources -l 中的内容替换为: http://gems.ruby-china.org/ 2.更新gem 使用的语句为:gem update --system 3.安装cocoapods  方法语句为:sudo gem install -n /usr/local/bin cocoapods 这样就可以使用pod 语句了 可以安装你在Podfile中的加入的三方控件 pod install

Unable to download data from http://ruby.taobao.org/ &amp; don&#39;t have write permissions for the /Library/Ruby/Gems/2.0.0 directory.

安装cocoapods,记录两个问题! 1.镜像已经替换成了 http://ruby.taobao.org/, 还是不能不能安装cocoapods, 报错:Unable to download data from http://ruby.taobao.org/ - bad response Not Found 404 (http://ruby.taobao.org/latest_specs.4.8.gz) 如图: 原来是ruby.taobao.org已经停止基于 HTTP 协议的镜像服务, 启用

eclipse搭建ruby开发环境,安装插件RDT,dltk,gems

因为Metasploit模块是用ruby写的,看不懂,本着急切的钻研精神学习一下. 由于自己做java出身,用惯了eclipse,在接触ruby的时候需要快速上手,就选择了java的开发环境搭建ruby. 其实Metasploit更合理的是搭建linux下的vim环境,因为自己做过一段c开发,知道搭建配置和使用熟练起来的周期更长,所以放在已经掌握ruby开发后再做. 但是在eclipse和Myeclipse环境下也不轻松,费了3个小时都不成功.过程如下. 1,http://sourceforge

Rails3:使用bundler管理gems

Rails3:使用bundler管理gems bundler 是一套为了 Rails3 所打造的全新 Gem dependencies 管理工具:一套基于 Rubygems 的更高阶套件管理工具,适合让 Application 管理多套 Gems 依存关係的複杂情境.而你在 Rails3 中 (Bundler 不只用在 Rails3,其他例如 Sinatra 或是 Rails2 也都可以使用) 要使用的 Gems,也都必须宣告在它的 Gemfile 裡,没写在裡面的话,就算手动 require

(dp)HDU6199- gems gems gems

gems gems gems Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 476    Accepted Submission(s): 53 Problem Description Now there are n gems, each of which has its own value. Alice and Bob play a g

ACM: Racing Gems - 最长递增序列

Racing Gems   You are playing a racing game.  Your character starts at the x axis (y = 0) and proceeds up the      race track, which has a boundary at the line x = 0 and another at x = w.  You  may start the race       at any horizontal position you

../gems/json-1.8.0/lib/json/common.rb:67: [BUG] Segmentation fault

在执行rails 命令时出现: [email protected]:~/ashelf$ rails s /home/diudiugirl/.rvm/gems/ruby-1.9.3-p545/gems/json-1.8.0/lib/json/common.rb:67: [BUG] Segmentation fault ruby 1.9.3p545 (2014-02-24 revision 45159) [x86_64-linux] -- Control frame information ----

解题报告 之 ZOJ2332 Gems

解题报告 之 ZOJ2332 Gems Description Wealthy alsomagic! Supernatural alsomagic! But also poor alsomagic! Because he is now puzzled by a problem, and will go crazy if you can't help him. alsomagic has a lot of gems with different colors and shapes. His sup

hdu 4778 Gems Fight!(状态压缩+博弈+记忆化)

Gems Fight! Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 327680/327680 K (Java/Others) Total Submission(s): 1383    Accepted Submission(s): 587 Problem Description Alice and Bob are playing "Gems Fight!": There are Gems of G differe