题解：P4209 学习小组

· · 题解

Solution

那个啥，平方很难处理。假如说增加一个人，平方从 x^2 增加到 (x+1)^2，作差一下发现新加一个人的代价是 2x+1，然后对于每一个小组都加 n 条边即可。

然后是每个人至少选一个，如果明明能选却没选让给别人这不是最优的。首先拆点后每个人都有 k 的流量，给他最多 k-1 个不选的机会，那这样跑出来的最大流一定能保证参与的人最多。所以需要额外让每个学生向汇点连流量为 k-1、费用为 0 的边。
原因：存在一种流法，就是每个人都只选一个，这样选出来的最大流一定保证人最多，所以其他与该最大流大小相等的也是符合要求的。

其他的建边很简单，不赘述。

:::success[code]


#include <bits/stdc++.h>
using namespace std;
struct node{int u,v,w,c;};
int n,m,k,s,t=381,x,f[95],d[385],flag[385],ans;
bool vis[385];
char ch;
vector<node> edges;
vector<int> e[385];
queue<int> q;
void add(int u,int v,int w,int c){
    edges.push_back({u,v,w,c});
    edges.push_back({v,u,0,-c});
    e[u].push_back(edges.size()-2);
    e[v].push_back(edges.size()-1);
}
bool bfs(){
    memset(d,0x3f,sizeof d);
    while(!q.empty()) q.pop(); 
    d[s]=0,q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        vis[u]=0;
        for(auto to:e[u]){
            int v=edges[to].v;
            if(d[v]>d[u]+edges[to].c&&edges[to].w){
                d[v]=d[u]+edges[to].c;
                if(!vis[v]) q.push(v),vis[v]=1;
            }
        }
    }
    return d[t]<1e9;
}
int dfs(int u,int flow){
    if(u==t) return flow;
    int sum=0;
    vis[u]=1;
    for(int i = flag[u];i<e[u].size();i++){
        int v=edges[e[u][i]].v;
        if(!vis[v]&&edges[e[u][i]].w&&d[v]==d[u]+edges[e[u][i]].c){
            int tmp=dfs(v,min(flow,edges[e[u][i]].w));
            sum+=tmp,flow-=tmp,edges[e[u][i]].w-=tmp,edges[e[u][i]^1].w+=tmp,ans+=edges[e[u][i]].c*tmp;
            if(!flow) break;
        }
    }
    vis[u]=0;
    if(!sum) d[u]=-1;
    return sum;
}
int dinic(){
    while(bfs()){
        memset(flag,0,sizeof flag);
        dfs(s,1e9);
    }
    return ans;
}
signed main(){
    cin>>n>>m>>k;
    for(int i = 1;i<=m;i++){
        cin>>x;
        for(int j = 1;j<=2*n-1;j+=2)
            add(i+n,t,1,j*x);
    }
    for(int i = 1;i<=m;i++) cin>>f[i];
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++){
            cin>>ch;
            if(ch=='1') add(i,j+n,1,-f[j]);
        }
    for(int i = 1;i<=n;i++) add(s,i,k,0),add(i,t,k-1,0);
    cout<<dinic();
    return 0;
}