频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
BZOJ 1934([Shoi2007]Vote 善意的投票-最小割)
2013-06-23 16:55:00           
收藏   我要投稿

[Submit][Status][Discuss]
Description
幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说,这个问题并不是很重要,于是他们决定发扬谦让精神。虽然每个人都有自己的主见,但是为了照顾一下自己朋友的想法,他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。 我们的问题就是,每位小朋友应该怎样投票,才能使冲突数最小?
Input
第一行只有两个整数n,m,保证有2≤n≤300,1≤m≤n(n-1)/2。其中n代表总人数,m代表好朋友的对数。文件第二行有n个整数,第i个整数代表第i个小朋友的意愿,当它为1时表示同意睡觉,当它为0时表示反对睡觉。接下来文件还有m行,每行有两个整数i,j。表示i,j是一对好朋友,我们保证任何两对i,j不会重复。
Output
只需要输出一个整数,即可能的最小冲突数。
Sample Input
3 3
1 0 0
1 2
1 3
3 2

Sample Output
1
HINT
在第一个例子中,所有小朋友都投赞成票就能得到最优解

Source
Day2

[Submit][Status][Discuss]
想到是最小割就好办了呢。。。。(喂我没想到啊混蛋)

S向赞成的小孩连,T向反对的连,好友互相连,容量皆为1

OK(根据最小割定义,最小割切的都是从S向T的有向边【话外:反向呢?答:无视】,显然成立)


[cpp]  #include<cstdio>  
#include<cstring>  
#include<cstdlib>  
#include<algorithm>  
#include<functional>  
#include<iostream>  
#include<cmath>  
#include<cctype>  
#include<ctime>  
using namespace std; 
#define For(i,n) for(int i=1;i<=n;i++)  
#define Fork(i,k,n) for(int i=k;i<=n;i++)  
#define Rep(i,n) for(int i=0;i<n;i++)  
#define ForD(i,n) for(int i=n;i;i--)  
#define RepD(i,n) for(int i=n;i>=0;i--)  
#define Forp(x) for(int p=pre[x];p;p=next[p])  
#define Lson (x<<1)  
#define Rson ((x<<1)+1)  
#define MEM(a) memset(a,0,sizeof(a));  
#define MEMI(a) memset(a,127,sizeof(a));  
#define MEMi(a) memset(a,128,sizeof(a));  
#define INF (2139062143)  
#define F (100000007)  
#define MAXN (300+2+10)  
#define MAXM (MAXN*MAXN*4)   
long long mul(long long a,long long b){return (a*b)%F;} 
long long add(long long a,long long b){return (a+b)%F;} 
long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;} 
int edge[MAXM],pre[MAXN]={0},next[MAXM],weight[MAXM],size=1; 
void addedge(int u,int v,int w) 

    edge[++size]=v; 
    weight[size]=w; 
    next[size]=pre[u]; 
    pre[u]=size; 

void addedge2(int u,int v,int w){addedge(u,v,w),addedge(v,u,0);} 
int d[MAXN]={0},cnt[MAXN]={0},s,t; 
int totflow=0; 
int sap(int x,int flow) 

    if (x==t) return flow; 
    int nowflow=0; 
    Forp(x) 
    { 
        int &v=edge[p]; 
        if (d[v]==d[x]-1&&weight[p]>0) 
        { 
            int fl=sap(v,min(flow,weight[p])); 
            weight[p]-=fl,weight[p^1]+=fl,flow-=fl,nowflow+=fl; 
            if (!flow) return nowflow; 
        } 
    } 
    if (!(--cnt[d[x]++])) d[s]=t+1; 
    cnt[d[x]]++; 
    return nowflow;  
}  
int n,m,a[MAXN]; 
int main() 

//  freopen("conflict.in","r",stdin);  
//  freopen("conflict.out","w",stdout);  
    scanf("%d%d",&n,&m); 
    s=n+1,t=s+1; 
    For(i,n)  
    { 
        scanf("%d",&a[i]); 
        if (a[i]) addedge2(s,i,1); 
        else addedge2(i,t,1); 
    } 
    For(i,m) 
    { 
        int u,v; 
        scanf("%d%d",&u,&v); 
        addedge(u,v,1);addedge(v,u,1); 
    } 
    cnt[0]=n+2; 
    while (d[s]<=t) totflow+=sap(s,INF); 
    cout<<totflow<<endl; 
 
    return 0; 

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define MAXN (300+2+10)
#define MAXM (MAXN*MAXN*4)
long long mul(long long a,long long b){return (a*b)%F;}
long long add(long long a,long long b){return (a+b)%F;}
long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}
int edge[MAXM],pre[MAXN]={0},next[MAXM],weight[MAXM],size=1;
void addedge(int u,int v,int w)
{
 edge[++size]=v;
 weight[size]=w;
 next[size]=pre[u];
 pre[u]=size;
}
void addedge2(int u,int v,int w){addedge(u,v,w),addedge(v,u,0);}
int d[MAXN]={0},cnt[MAXN]={0},s,t;
int totflow=0;
int sap(int x,int flow)
{
 if (x==t) return flow;
 int nowflow=0;
 Forp(x)
 {
  int &v=edge[p];
  if (d[v]==d[x]-1&&weight[p]>0)
  {
   int fl=sap(v,min(flow,weight[p]));
   weight[p]-=fl,weight[p^1]+=fl,flow-=fl,nowflow+=fl;
   if (!flow) return nowflow;
  }
 }
 if (!(--cnt[d[x]++])) d[s]=t+1;
 cnt[d[x]]++;
 return nowflow;
}
int n,m,a[MAXN];
int main()
{
// freopen("conflict.in","r",stdin);
// freopen("conflict.out","w",stdout);
 scanf("%d%d",&n,&m);
 s=n+1,t=s+1;
 For(i,n)
 {
  scanf("%d",&a[i]);
  if (a[i]) addedge2(s,i,1);
  else addedge2(i,t,1);
 }
 For(i,m)
 {
  int u,v;
  scanf("%d%d",&u,&v);
  addedge(u,v,1);addedge(v,u,1);
 }
 cnt[0]=n+2;
 while (d[s]<=t) totflow+=sap(s,INF);
 cout<<totflow<<endl;

 return 0;
}


 

点击复制链接 与好友分享!回本站首页
相关TAG标签 善意
上一篇:整数因子分解问题的递归算法
下一篇:C++输出斐波那契数列的几种方法
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站