[BZOJ 1934]善意的投票/[BZOJ 2768]冠军调查

这个是一道题啊……不过都是挺经典的问题……

建图是这样的:支持0的从[tex]S[/tex]向此点连一条容量为1的边,支持1的就向[tex]T[/tex]连一条长度为1的边,朋友之间连一条长度为1的边。跑一遍最小割即可。

这个的解释?最优情况下任何人违背自己的意见都是因为怕和朋友冲突,和朋友冲突则是因为没有违背自己的意见(废话)。所以拆了最小割就解决掉了所有冲突问题。

代码:

/**************************************************************
    Problem: 2768
    User: danihao123
    Language: C++
    Result: Accepted
    Time:60 ms
    Memory:7668 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=305;
namespace Dinic{
    struct Edge{
        int u,v,cap,flow;
    };
    vector<Edge> edges;
    vector<int> G[maxn];
    int s,t;
    int m;
    inline void AddEdge(int u,int v,int cap){
        edges.push_back((Edge){u,v,cap,0});
        edges.push_back((Edge){v,u,0,0});
        m=edges.size();
        G[u].push_back(m-2);
        G[v].push_back(m-1);
    }
    bool vis[maxn];
    int cur[maxn],d[maxn];
    bool bfs(){
        register int i,u;
        queue<int> Q;
        memset(vis,0,sizeof(vis));
        Q.push(s);
        d[s]=0;
        vis[s]=true;
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            for(i=0;i<G[u].size();i++){
                Edge& e=edges[G[u][i]];
                if(!vis[e.v] && e.cap>e.flow){
                    d[e.v]=d[u]+1;
                    Q.push(e.v);
                    vis[e.v]=true;
                }
            }
        }
        return vis[t];
    }
    int dfs(int x,int a){
        if(x==t || a==0)
            return a;
        int f,flow=0;
        for(int& i=cur[x];i<G[x].size();i++){
            Edge& e=edges[G[x][i]];
            if((d[x]+1==d[e.v]) && ((f=dfs(e.v,min(a,e.cap-e.flow)))>0)){
                flow+=f;
                e.flow+=f;
                edges[G[x][i]^1].flow-=f;
                a-=f;
                if(a==0)
                    break;
            }
        }
        return flow;
    }
    int MinCut(int S,int T){
        register int ans=0;
        s=S;
        t=T;
        while(bfs()){
            memset(cur,0,sizeof(cur));
            ans+=dfs(s,0x7fffffff);
        }
        return ans;
    }
};
int main(){
    int n,m;
    int u,v;
    register int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&u);
        if(!u){
            Dinic::AddEdge(0,i,1);
        }else{
            Dinic::AddEdge(i,n+1,1);
        }
    }
    for(i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        Dinic::AddEdge(u,v,1);
        Dinic::AddEdge(v,u,1);
    }
    printf("%d\n",Dinic::MinCut(0,n+1));
    return 0;
}

[BZOJ 1022]小约翰的游戏

这个题是比较特殊的游戏。因为扩展出最后一个状态的人会输。这种游戏称为Anti-SG游戏。

解决这种题,需要SJ定理:先手必胜当且仅当游戏的SG函数为0而存在一个单一游戏的SG函数大于1,或整个游戏的SG函数不为0且没有任何单一游戏的SG函数大于1。问题迎刃而解。

代码:

/**************************************************************
    Problem: 1022
    User: danihao123
    Language: C++
    Result: Accepted
    Time:40 ms
    Memory:820 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
    register int i,last;
    int n,temp,T;
    bool obey_1;
    scanf("%d",&T);
    while(T--){
        obey_1=false;
        last=0;
        scanf("%d",&n);
        for(i=1;i<=n;i++){
            scanf("%d",&temp);
            if(temp>1){
                obey_1=true;
            }
            last=last^temp;
        }
        if((last!=0 && obey_1) || (last==0 && !obey_1)){
            puts("John");
        }else{
            puts("Brother");
        }
    }
    return 0;
}