题目背景

小Z在机房。

题目描述

小Z和其它机房同学都面临一个艰难的抉择，那就是 要不要划水？

每个人都有自己的一个意见，有的人想做题，有的人想划水。

当然，每个人只能选择一个事情做。如果一个人做的事情和他想做的不同，那么他会产生1不满意度。

更棘手的是，他们之间一些人是朋友，如果两人是朋友，但是他们做的事情不同，那么会有1不满意度产生。

小Z不想看到大家闹得不高兴，他想知道，不满意度最小能是多少？

输入输出格式

输入格式：

 

第一行两个数字n,m 分别表示有n个人和m对朋友关系

第二行n个0/1，1表示想做题，0表示想划水。

然后是m行，每行两个数字a,b 表示a和b是朋友

 

输出格式：

 

输出只包含一个数字，表示最小的不满意度。

 

输入输出样例

输入样例#1：

3 10 1 01 2

输出样例#1：

1

说明

每个人都做自己想做的事情，但是1和2不同，所以答案是1.

还有答案是1的其它方案，可以证明这是最小的不满意度。

对于10%的数据，满足n<=10 m=10

对于30%的数据，满足n,m<=20

对于100%的数据，满足n<=300 m<=n*(n-1)/2

保证没有重复的朋友关系。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int read(){ int t=1,num=0; char c=getchar(); while(c>'9'||c<'0'){ if(c=='-')t=-1;c=getchar();} while(c>='0'&&c<='9'){num=num*10+c-'0';c=getchar();} return num*t;}const int INF=0x7fffffff-199;struct Yzyet{ int t,c,r;};vector
           
             g[310];int n,m,iter[310],lev[310];void add(int f,int t,int c){ g[f].push_back((Yzyet){t,c,g[t].size()}); g[t].push_back((Yzyet){f,0,g[f].size()-1});}void bfs(int s){ memset(lev,0,sizeof(lev)); queue
            
             q; lev[s]=1; q.push(s); while(!q.empty()){ int v=q.front();q.pop(); for(int i=0;i
             
              0&&lev[e.t]==0){ lev[e.t]=lev[v]+1; q.push(e.t); } } }}int dfs(int v,int t,int f){ if(v==t)return f; for(int &i=iter[v];i
              
               0&&lev[v]+1==lev[e.t]){ int d=dfs(e.t,t,min(f,e.c)); if(d>0){ e.c-=d; g[e.t][e.r].c+=d; return d; } } } return 0;}int flow(int s,int t){ int fl=0; while(1){ bfs(s); if(lev[t]==0)return fl; memset(iter,0,sizeof(iter)); int f; while((f=dfs(s,t,INF))>0)fl+=f; }}int main(){ n=read();m=read(); for(int i=1;i<=n;i++){ int h=read(); if(h==0)add(0,i,1); else add(i,n+1,1); } for(int i=1;i<=m;i++){ int a,b; a=read();b=read(); add(a,b,1);add(b,a,1); } printf("%d",flow(0,n+1)); return 0;}
              
             
            
           
          
         
        
       
      
     

本文由Yzyet编写，网址为www.cnblogs.com/Yzyet。非Yzyet同意，禁止转载，侵权者必究。