更向天涯

用户名：20110618li

访问量：42387

签　名：

向天涯进发！

等　　级
排　　名	12
经　　验	25728
参赛次数	28
文章发表	502
年　　龄	45
在职情况	在职
学　　校	柏苑中心小学
专　　业	编程

　　自我简介：

无情未必真豪杰，怜子如何不丈夫。

TA的其他文章

1402: 简单的字符串
浏览：20

2997: 梯形面积
浏览：1821

3002: 买图书（不用再抱怨有个测试点出错了，真正的测试点回来了——最新代码）
浏览：188

你可能喜欢

C语言程序设计教程（第三版）课后习题6.10 （Java代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

1587: 蓝桥杯算法训练VIP-Buying Sets

　　作者: 更向天涯　　　　发表时间：2023-01-13 08:32:52 浏览：118　|　评论：0　

原题链接：蓝桥杯算法训练VIP-Buying Sets

```cpp
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=305,INF=1<<30;
int setnum,weight[MAXN],match[MAXN],visited[MAXN],posweight=0,deep[MAXN];
vector<int>sets[MAXN];
struct Edge
{
    int from,to,cap,flow;
};
vector<int>G[MAXN];
vector<Edge>edges;
bool dfs(int u)
{
    for(int i=0;i<sets[u].size();i++)
    {
        int v=sets[u][i];
        if(visited[v])
            continue;
        visited[v]=1;
        if(!match[v]||dfs(match[v]))
        {
            match[v]=u;
            return true;
        }
    }
    return false;
}
void hungary()
{
    memset(match,0,sizeof(match));
    for(int i=1;i<=setnum;i++)
    {
        memset(visited,0,sizeof(visited));
        dfs(i);
    }
    return;
}
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 m=edges.size();
    G[u].push_back(m-2);
    G[v].push_back(m-1);
    return;
}
void init()
{
    hungary();
    for(int i=1;i<=setnum;i++)
    {
        if(weight[i]<0)
        {
            addedge(0,i,-weight[i]);
            posweight-=weight[i];
        }
        else
            addedge(i,setnum+1,weight[i]);
    }
    for(int i=1;i<=setnum;i++)
        for(int j=0;j<sets[i].size();j++)
        {
            int v=sets[i][j];
            if(match[v]!=i)addedge(i,match[v],INF);
        }
    return;
}
bool bfs()
{
    memset(deep,0,sizeof(deep));
    queue<int>Q;
    Q.push(0);
    deep[0]=1;
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        for(int i=0;i<G[u].size();i++)
        {
            Edge edge=edges[G[u][i]];
            if(!deep[edge.to]&&edge.cap>edge.flow)
            {
                deep[edge.to]=deep[edge.from]+1;
                Q.push(edge.to);
            }
        }
    }
    return deep[setnum+1];
}
int dinc(int u,int pref)
{
    if(u==setnum+1)
        return pref;
    int f=0;
    for(int i=0;i<G[u].size();i++)
    {
        int t=G[u][i];
        Edge edge=edges[t];
        if(edge.cap>edge.flow&&deep[edge.from]==deep[edge.to]-1)
        {
            int temp=min(pref,edge.cap-edge.flow),x=dinc(edge.to,temp);
            edges[t].flow+=x;
            edges[t^1].flow-=x;
            f+=x;
            pref-=x;
        }
    }
    return f;
}
int solve()
{
    init();
    int maxflow=0;
    while(bfs())
        maxflow+=dinc(0,1<<30);
    return posweight-maxflow;
}
int main()
{
    cin>>setnum;
    int k,ele;
    for(int i=1;i<=setnum;i++)
    {
        cin>>k;
        for(int j=0;j<k;j++)
        {
            cin>>ele;
            sets[i].push_back(ele);
        }
    }
    for(int i=1;i<=setnum;i++)
        cin>>weight[i];
    int ans=-solve();
    if(ans>0)
        cout<<0;
    else
        cout<<ans;
    return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

更向天涯

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.10 （Java代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

点我有惊喜！你懂得！

破解简单密码（C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

1587: 蓝桥杯算法训练VIP-Buying Sets

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言训练-斐波纳契数列（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【计算球体积】（C语言代码）

数字游戏（C++代码）

IP判断（C语言代码）

企业奖金发放（C语言代码）

数组输出（C语言代码）

C语言程序设计教程（第三版）课后习题12.1 （C语言代码）

第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略

更向天涯

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.10 （Java代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

点我有惊喜！你懂得！

破解简单密码 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

1587: 蓝桥杯算法训练VIP-Buying Sets

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言训练-斐波纳契数列 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【计算球体积】 （C语言代码）

数字游戏 （C++代码）

IP判断 （C语言代码）

企业奖金发放 （C语言代码）

数组输出 （C语言代码）

C语言程序设计教程（第三版）课后习题12.1 （C语言代码）

第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略

破解简单密码（C语言代码）

　　评论区

C语言训练-斐波纳契数列（C语言代码）

【计算球体积】（C语言代码）

数字游戏（C++代码）

IP判断（C语言代码）

企业奖金发放（C语言代码）

数组输出（C语言代码）