luoguP2057善意的投票

谁践踏了优雅 2021-12-23 01:35 265阅读 0赞

### 理解下题意： ###

题意大致就是有n个人有两种不同的意见并且有许多朋友，需要让朋友间尽可能的统一意见（少发生冲突），如果一个人违反自己的本意也算冲突，求最少的冲突。。。

### 思路： ###

明眼人直接发现是最小割，两种意见可以看作源点S和T，我们需要做的是割最少的边使得S和T成为两个不同的集合，解释：割掉的边相当于1次冲突（因为若某边被割走，则显然这条边相连的两个点分别通向了S和T，所以算是一次冲突），当S和T还连通时则必然存在一条路径，这样肯定会有冲突，所以需要使得S和T孤立。

### 实现： ###

实现时这样建图：直接将S连向同意的人，T连向不同意的人，若两人是朋友，则在他们之间连一条双向边（这里有些人不理解：若两个人有冲突，则只需要其中任意一个人改变意见就行了，简单说是让a同意b的意见或者b同意a的意见，所以只需割掉一条边满足一种情况就可以了，但是有两种情况，所以建双向边）。最后就是求最小割了，直接套上最大流的模板就ok了。

### 代码： ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <vector>
    #include <queue>
    using namespace std;
    const int MAXN = 1000;
    const int INF = 0x3f3f3f3;
    int n,m;
    struct Edge{
        int u,v,cap,flow;
    };
    vector<Edge> edges;
    vector<int> G[MAXN];
    void addedge(int u,int v,int cap){
        edges.push_back((Edge){u,v,cap,0});
        edges.push_back((Edge){v,u,0,0});
        int cnt=edges.size();
        G[u].push_back(cnt-2);
        G[v].push_back(cnt-1);   
    }
    int cur[MAXN],vis[MAXN],dep[MAXN],s,t;
    int dfs(int x,int a){
        if(x==t||a==0)
            return a;
        int flow=0,f=0;
        for(int &i=cur[x];i<G[x].size();i++){
            Edge &e = edges[G[x][i]];
            if(dep[e.v]==dep[x]+1&&(f=dfs(e.v,min(a,e.cap-e.flow)))>0){
                e.flow+=f;
                edges[G[x][i]^1].flow-=f;
                a-=f;
                flow+=f;
                if(!a)
                    break;
            }
        }
        return flow;
    }
    queue<int> q;
    bool bfs(){
        memset(vis,0,sizeof(vis));
        q.push(s);
        vis[s]=true;
        dep[s]=0;
        while(!q.empty()){
            int x=q.front();
            q.pop();
            for(int i=0;i<G[x].size();i++){
                Edge &e = edges[G[x][i]];
                if(e.cap>e.flow&&(!vis[e.v])){
                    vis[e.v]=true;
                    dep[e.v]=dep[x]+1;
                    q.push(e.v);
                }
            }
        }
        return vis[t];
    }
    int dinic(){
        int flow=0;
        while(bfs()){
            memset(cur,0,sizeof(cur));
            flow+=dfs(s,INF);
        }
        return flow;
    }
    int main(){
        s=MAXN-2;
        t=MAXN-3;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            int x;
            scanf("%d",&x);
            if(x)
                addedge(s,i,1);
            else
                addedge(i,t,1);
        }
        for(int i=1;i<=m;i++){  
            int a,b;
            scanf("%d%d",&a,&b);
            addedge(a,b,1);
            addedge(b,a,1);
        }
        printf("%d",dinic());
        return 0;
    }

善意的投票

转载于:https://www.cnblogs.com/zhouxuanbodl/p/10807709.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/e2a4b040a824490b855a85b870e4b0da.png