[JLOI2010]冠军调查 |

[JLOI2010]冠军调查同[SHOI2007]Vote 善意的投票
看到这种题目就知道要跑网络流啦。只要把赞成的连原点流量为1，反对连汇点流量为1，其他每个朋友互相连一条流量为一的边，然后跑一遍最短路就好。

#include<set>
#include<map>
#include<list>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define qread(x) x=read()
#define mes(x,y) memset(x,y,sizeof(x))
#define mpy(x,y) memcpy(x,y,sizeof(x))
#define Maxn 302
#define INF 2147483647
inline int read(){
    int f=1,x=0;char ch=getchar();
    while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}
int n,m,ans;
struct Edge{
    int x,y,c,next,other;
}E[Maxn*Maxn+1];int len,first[Maxn+3];
void ins(int x,int y,int c){
    len++;
    E[len].x=x;E[len].y=y;E[len].c=c;
    E[len].next=first[x];first[x]=len;E[len].other=len+1;
    len++;
    E[len].x=y;E[len].y=x;E[len].c=0;
    E[len].next=first[y];first[y]=len;E[len].other=len-1;
}
int st,ed,h[Maxn+3];
bool v[Maxn+3];
std::queue<int>q;
bool bt(){
    q.push(st);
    mes(h,0);h[st]=1;
    mes(v,false);v[st]=true;
    while(q.empty()==false){
        int x=q.front();
        for(int k=first[x];k>0;k=E[k].next){
            int y=E[k].y;
            if(h[y]==0&&E[k].c>0){
                h[y]=h[x]+1;
                if(v[y]==false){
                    v[y]=true;
                    q.push(y);
                }
            }
        }
        v[x]=false;
        q.pop();
    }
    if(h[ed]>0)return true;
    else return false;
}
int findflow(int x,int f){
    if(x==ed)return f;
    int s=0,tmp;
    for(int k=first[x];k>0;k=E[k].next){
        int y=E[k].y;
        if(E[k].c>0&&h[y]==h[x]+1&&s<f){
            tmp=findflow(y,std::min(E[k].c,f-s));
            s+=tmp;
            E[k].c-=tmp;E[E[k].other].c+=tmp;
        }
    }
    if(s==0)h[x]=0;
    return s;
}
int main(){
    qread(n);qread(m);
    st=n+1;ed=st+1;
    len=0;mes(first,0);
    for(int i=1;i<=n;i++){
        int qread(x);
        if(x==1)ins(st,i,1);
        else ins(i,ed,1);
    }
    for(int i=1;i<=m;i++){
        int qread(x),qread(y);
        ins(x,y,1);ins(y,x,1);
    }
    ans=0;
    while(bt()==true)ans+=findflow(st,INF);
    printf("%d\n",ans);
}

#include<set>

#include<map>

#include<list>

#include<queue>

#include<cmath>

#include<vector>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define qread(x) x=read()

#define mes(x,y) memset(x,y,sizeof(x))

#define mpy(x,y) memcpy(x,y,sizeof(x))

#define Maxn 302

#define INF 2147483647

inline int read(){

int f=1,x=0;char ch=getchar();

while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}

return x*f;

}

int n,m,ans;

struct Edge{

int x,y,c,next,other;

}E[Maxn*Maxn+1];int len,first[Maxn+3];

void ins(int x,int y,int c){

len++;

E[len].x=x;E[len].y=y;E[len].c=c;

E[len].next=first[x];first[x]=len;E[len].other=len+1;

len++;

E[len].x=y;E[len].y=x;E[len].c=0;

E[len].next=first[y];first[y]=len;E[len].other=len-1;

}

int st,ed,h[Maxn+3];

bool v[Maxn+3];

std::queue<int>q;

bool bt(){

q.push(st);

mes(h,0);h[st]=1;

mes(v,false);v[st]=true;

while(q.empty()==false){

int x=q.front();

for(int k=first[x];k>0;k=E[k].next){

int y=E[k].y;

if(h[y]==0&&E[k].c>0){

h[y]=h[x]+1;

if(v[y]==false){

v[y]=true;

q.push(y);

}

v[x]=false;

q.pop();

}

if(h[ed]>0)return true;

else return false;

}

int findflow(int x,int f){

if(x==ed)return f;

int s=0,tmp;

for(int k=first[x];k>0;k=E[k].next){

int y=E[k].y;

if(E[k].c>0&&h[y]==h[x]+1&&s<f){

tmp=findflow(y,std::min(E[k].c,f-s));

s+=tmp;

E[k].c-=tmp;E[E[k].other].c+=tmp;

}

if(s==0)h[x]=0;

return s;

}

int main(){

qread(n);qread(m);

st=n+1;ed=st+1;

len=0;mes(first,0);

for(int i=1;i<=n;i++){

int qread(x);

if(x==1)ins(st,i,1);

else ins(i,ed,1);

}

for(int i=1;i<=m;i++){

int qread(x),qread(y);

ins(x,y,1);ins(y,x,1);

}

ans=0;

while(bt()==true)ans+=findflow(st,INF);

printf("%d\n",ans);

}

发表评论 取消回复

发表评论取消回复