牛客练习赛65 游走配对 费用流

题目链接:https://ac.nowcoder.com/acm/contest/5961/E
题目大意:
图片说明
思路:拆点,在出点向进点连接q条边。第k条边的流量为1,费用为a+(k-1)*b。对于原图的边,出点到入点连接流量为q。费用为0的边。
然后源点0到所有x的入点连接费用为0,流量为1的边。同理:所以y的出点到汇点点2n+1连接费用为0,流量为1的边。跑个最小费用最大流。

#include<bits/stdc++.h>
#define MAXN_ 5050
#define INF 0x3f3f3f3f
#define P pair<int,int>
using namespace std;
struct edge
{
    int to,cap,cost,rev;
};
int n,N,m,flow,s,t,cap,res,cost,from,to,h[MAXN_];
std::vector<edge> G[MAXN_];
int dist[MAXN_],prevv[MAXN_],preve[MAXN_]; // 前驱节点和对应边
inline void add()
{
    //cout<<from<<" "<<to<<" "<<cap<<" "<<cost<<endl;
    G[from].push_back((edge)
    {
        to,cap,cost,(int)G[to].size()
    });
    G[to].push_back((edge)
    {
        from,0,-cost,(int)G[from].size()-1
    });
} // 在vector 之中找到边的位置所在!
inline int read()
{
    int x=0;
    char c=getchar();
    bool flag=0;
    while(c<'0'||c>'9')
    {
        if(c=='-')flag=1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return flag?-x:x;
}
inline void min_cost_flow(int s,int t,int f)
{
    memset(h,0,sizeof(h));
    while(f > 0)
    {
        priority_queue<P,vector<P>, greater<P> > D;
        memset(dist,INF,sizeof dist);
        dist[s] = 0;
        D.push(P(0,s));
        while(!D.empty())
        {
            P now = D.top();
            D.pop();
            if(dist[now.second] < now.first)
            {
                continue;
            }
            int v = now.second;
            for(int i=0; i<(int)G[v].size(); ++i)
            {
                edge &e = G[v][i];
                if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to])
                {
                    dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    D.push(P(dist[e.to],e.to));
                }
            }
        }
        // 无法增广 , 就是找到了答案了!
        if(dist[t] == INF) break;
        for(int i=1; i<=N; ++i)
        {
            h[i] += dist[i];
        }
        int d = f;
        for(int v = t; v != s; v = prevv[v])
        {
            d = min(d,G[prevv[v]][preve[v]].cap);
        }
        f -= d;
        flow += d;
        res += d * h[t];
        for(int v=t; v!=s; v=prevv[v])
        {
            edge &e = G[prevv[v]][preve[v]];
            e.cap -= d;
            G[v][e.rev].cap += d;
        }
    }
}
int main(){

    int q, a, b; scanf("%d%d%d", &n, &m, &q);
    s=0, t=2*n+1; N=t;
    for(int i=1; i<=n; i++){
        scanf("%d%d", &a, &b);
        from = i;  to = i+n;
        for(int k=1; k<=q; k++){
            cap = 1;
            cost = a+(k-1)*b;
            add();
        }
    }
    for(int i=1; i<=m; i++){
        scanf("%d%d", &a, &b);
        from = a+n;  to = b; cap = q; cost = 0;
        add();
        from = b+n;  to = a; cap = q; cost = 0;
        add();
    }
    for(int i=1; i<=q; i++){
        scanf("%d", &a);
        from = s;  to = a; cap = 1; cost = 0;
        add();
    }
    for(int i=1; i<=q; i++){
        scanf("%d", &b);
        from = b+n;  to = t; cap = 1; cost = 0;
        add();
    }
    min_cost_flow(s,t,INF);
    printf("%d\n", res);

    return 0;
}

全部评论

相关推荐

点赞 评论 收藏
分享
群星之怒:1.照片可以换更好一点的,可以适量P图,带一些发型,遮住额头,最好穿的正式一点,可以适当P图。2.内容太少。建议添加的:求职意向(随着投递岗位动态更改);项目经历(内容太少了建议添加一些说明,技术栈:用到了什么技术,还有你是怎么实现的,比如如何确保数据传输稳定的,角色注册用到了什么技术等等。)项目经历是大头,没有实习是硬伤,如果项目经理不突出的话基本很难过简历筛。3.有些内容不必要,比如自我评价,校内实践。如果实践和工作无关千万别写,不如多丰富丰富项目。4.排版建议:建议排版是先基础信息,然后教育背景(要突出和工作相关的课程),然后专业技能(一定要简短,不要长篇大论,写你会什么,会的程度就可以),然后是项目经历(一定要详细,占整个简历一定要超过一半,甚至超过百分之70都可以)。最后如果有一部分空白的话可以填补上校内获得的专业相关的奖项,没有就写点校园经历和自我评价。5.技术一定要够硬,禁得住拷打。还有作息尽量保证正常,不要太焦虑。我24双非本科还是非科班,秋招春招各找了一段实习结果都没有转正,当时都想噶了,最后6月份在校的尾巴也找到一份工作干到现在,找工作有时很看运气的不要急着自我否定。 加油
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务