1305: [CQOI2009]dance跳舞

题目： 

题解：

　　 一眼网络流基础建模...然后就GG了

　　 二分答案+拆点建边+最大流判断：

　　 把男女生拆为男1，男2，女1，女2

　　 1、男1和男2还有女1和女2之间连边，流量为约束条件k

　　 2、st连男1，女2连ed，流量为二分的mid

　　 3、如果男生i喜欢女生j，就将男1与女2相连（不在约束条件内）

　　 4、如果不喜欢，就将男2与女1相连（在约束条件内）

代码：

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 using namespace std;  7 char ss[55][55];  8 struct node  9 { 10     int x,y,c,next,other; 11 }a[2110000];int len,last[1110000]; 12 int st,ed,head,tail,n,k; 13 void ins(int x,int y,int c) 14 { 15     int k1,k2; 16     k1=++len; 17     a[len].x=x;a[len].y=y;a[len].c=c; 18     a[len].next=last[x];last[x]=len; 19      20     k2=++len; 21     a[len].x=y;a[len].y=x;a[len].c=0; 22     a[len].next=last[y];last[y]=len; 23      24     a[k1].other=k2; 25     a[k2].other=k1; 26 } 27 int h[1110000],list[1110000]; 28 bool bt_h() 29 { 30     memset(h,0,sizeof(h));h[st]=1; 31     head=1;tail=2;list[1]=st; 32     while(head!=tail) 33     { 34         int x=list[head]; 35         for(int k=last[x];k;k=a[k].next) 36         { 37             int y=a[k].y; 38             if(h[y]==0 && a[k].c) 39             { 40                 h[y]=h[x]+1; 41                 list[tail++]=y; 42             } 43         } 44         head++; 45     } 46     if(h[ed])return true; 47     return false; 48 } 49 int find_flow(int x,int flow) 50 { 51     if(x==ed)return flow; 52     int t,s=0; 53     for(int k=last[x];k;k=a[k].next)     54     { 55         int y=a[k].y; 56         if(h[y]==(h[x]+1) && a[k].c && s
          
           男2 79 } 80 for(int j=1;j<=n;j++) 81 { 82 ins(j+n*3,ed,cc); 83 ins(j+n,j+n*3,s2[j]+k);//女1-->女2 84 }*/ 85 for(int i=1;i<=n;i++)//男2-->女1 86 for(int j=1;j<=n;j++) 87 { 88 if(ss[i][j]=='Y')ins(i,j+n*3,1); 89 else ins(i+n*2,j+n,1); 90 } 91 } 92 bool check(int cnt) 93 { 94 build(cnt); 95 int ans=0; 96 while(bt_h()) 97 ans+=find_flow(st,999999999); 98 if(ans==n*cnt)return true; 99 return false;100 }101 int main()102 {103 scanf("%d%d",&n,&k);104 for(int i=1;i<=n;i++)scanf("%s",ss[i]+1);105 l=1;r=n;int sum=0;106 while(l<=r)107 {108 mid=(l+r)/2;109 if(check(mid))110 {111 l=mid+1;112 sum=mid;113 }114 else r=mid-1;115 }116 printf("%d\n",sum);117 return 0;118 }