hdu 4411 最小费用流

时间：2022-02-18 05:53:38

思路：主要就是要把一个每个城市拆为两个点，建一条容量为1，费用为-inf的边，保证每个城市都会被遍历。

/*最小费用最大流*/

#include<iostream>

#include<cstring>

#include<cstring>

#include<cmath>

#include<cstdio>

using namespace std;

const int Maxn = ;

const int inf = ;

struct Edge{

    int v;

    int val;

    int cost;

    int next;

}edge[Maxn*];

int head[Maxn],n,g[Maxn][Maxn],m,k;

int e;

int pre[Maxn], pos[Maxn];

int dis[Maxn], que[Maxn*];

bool vis[Maxn];

void add(int u, int v, int val, int cost)

{

    edge[e].v = v;

    edge[e].val = val;

    edge[e].cost = cost;

    edge[e].next = head[u];

    head[u] = e++;

    edge[e].v = u;

    edge[e].val = ;

    edge[e].cost = -cost;

    edge[e].next = head[v];

    head[v] = e++;

}

void init()

{

    memset(head,-,sizeof(head));

    for(int i=;i<Maxn;i++)

        for(int j=;j<Maxn;j++)

        g[i][j]=inf;

    e=;

}

bool spfa(int s, int t)

{

    int i;

    memset(pre, -, sizeof(pre));

    memset(vis, , sizeof(vis));

    int Head, tail;

    Head = tail = ;

    for(i = ; i < Maxn; i++)

        dis[i] = inf;

    que[tail++] = s;

    pre[s] = s;

    dis[s] = ;

    vis[s] = ;

    while(Head != tail)

    {

        int now = que[Head++];

        vis[now] = ;

        for(i=head[now]; i != -; i = edge[i].next)

        {

            int adj = edge[i].v;

            //cout<<now<<" "<<adj<<" "<<dis[now]<<" "<<edge[i].cost<<" "<<dis[adj]<<" "<<edge[i].val<<endl;

            if(edge[i].val >  && dis[now] + edge[i].cost < dis[adj])

            {

                dis[adj] = dis[now] + edge[i].cost;

                pre[adj] = now;

                pos[adj] = i;

                if(!vis[adj])

                {

                    vis[adj] = ;

                    que[tail++] = adj;

                }

            }

        }

    }

    return pre[t] != -;

}

int MinCostFlow(int s, int t, int flow)

{

    int i;

    int cost = ;

    flow = ;

    while(spfa(s, t))

    {

        int f = inf;

        for(i = t; i != s; i = pre[i])

        if (edge[pos[i]].val < f)

            f = edge[pos[i]].val;

            flow += f;

            cost += dis[t] * f;

            for(i = t; i != s; i = pre[i])

            {

                edge[pos[i]].val -= f;

                edge[pos[i] ^ ].val += f;

            }

       // cout<<cost<<endl;

    }

    return cost;

    // flow是最大流值

}

void floyd()

{

    int i,j,k;

    for(k=;k<=n;k++)

        for(i=;i<=n;i++)

        for(j=;j<=n;j++)

        {

            if(g[k][j]==inf) continue;

           g[i][j]=min(g[i][j],g[i][k]+g[k][j]);

        }

}

void build(int lim)

{

    memset(head,-,sizeof(head));

    e=;

    int ss = ;

    int s = *n+;

    int t = *n+;

    add(s,ss,lim,);

    for(int i=;i<=n;i++)

    {

        if(g[][i] < inf)

        {

            add(ss,i,,g[][i]);

            add(i+n,t,,g[i][]);

        }

        add(i,i+n,,-inf);

        for(int j=i+;j<=n;j++)

        {

            if(g[i][j] < inf)

            {

            add(i+n,j,,g[i][j]);

            }

        }

    }

    add(ss,t,k,);

    return;

}

int solve()

{

    int i,j;

    int ans;

    ans=inf;

    build(k);

    ans=min(ans,MinCostFlow(n+n+,n+n+,)+n*inf);

    return ans;

}

int main()

{

    int i,j,u,v,c;

    while(scanf("%d%d%d",&n,&m,&k)!=EOF,n||m||k)

    {

        init();

        for(i=;i<=m;i++)

        {

            scanf("%d%d%d",&u,&v,&c);

            if(g[u][v]>c)

            g[u][v]=g[v][u]=c;

        }

        floyd();

        printf("%d\n",solve());

    }

    return ;

}

相关文章