首页 > 代码库 > LA 3353 Optimal Bus Route Design 二分匹配和有向图中的环

LA 3353 Optimal Bus Route Design 二分匹配和有向图中的环

2024-07-03 12:25:54   217人阅读

题意：题目给出一个有向图 ， 找若干个圈，使得每个结点切好属于一个圈，并且所有圈的总长度最小 ， 如果没有满足条件的就输出 ‘N‘ 。

注意：1、有重边

2、如果有向边(u , v) ， (v , u)都存在 ， 它们的长度不一定相同。

解法： 刚看这个题目的时候，没有什么思路，知道是用二分匹配之后就更没思路了。这题的关键还是在于构图：

每个点分成入度点和出度点两个点，然后在从新建图，例如：u 分成 u1 ， u2 ， v 分成 v1 ， v2 ， 假如有 (u , v) 这条边 ， 那么就变成 ( u1 , v2)。 具体理解，可以自己画一个图。

建图之后再求“最优二分匹配” ， 那么得到的结果就是我们要求的。

这题可以学到：以后求有向图中的环 ， 可以用二分图来求。



代码：


#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;

#define maxn 120
#define INF 0xffffff

int grap[maxn][maxn];
int n;
int cx[maxn] , cy[maxn];
int lx[maxn] , ly[maxn];
int pre[maxn];
int s[maxn] , t[maxn];
int slack[maxn];

void init()
{
    memset(grap , -1 , sizeof(grap));
    memset(cx , -1 , sizeof(cx));
    memset(cy , -1 , sizeof(cy));
}

int findpath(int u)
{
    s[u] = 1;
    for(int i = 1; i <= n; i++)
    {
        if(grap[u][i] != -1)
        {
            if(lx[u]+ly[i]==grap[u][i] && !t[i])
            {
                t[i] = 1;
                if(cy[i] == -1 || findpath(cy[i]))
                {
                    cy[i] = u;
                    cx[u] = grap[u][i];
                    return 1;

                }
            }
            else slack[i] = min(slack[i] , grap[u][i]-lx[u]-ly[i]);
        }

    }
    return 0;
}

int match()
{
    int i , j;
    for(i = 1; i <= n; i++)
    {
        ly[i] = 0;
        lx[i] = INF;
        for(j = 1; j <= n; j++)
            if(grap[i][j] != -1)
                lx[i] = min(lx[i] , grap[i][j]);
    }
    for(i = 1; i <= n; i++)
    {
        for(; ;)
        {
             for(j = 1; j <= n; j++)
             {
                 s[j]=t[j] = 0;
                 slack[j] = INF;
             }
             if(findpath(i))  break;
             int a = INF;
             for(j = 1; j <= n; j++)
                if(!t[j]) a = min(a , slack[j]);
             if(a == INF)  return -1;
             for(j = 1; j <= n; j++)
             {
                 if(s[j])  lx[j] += a;
                 if(t[j])  ly[j] -= a;
             }
        }

    }
    return 1;
}

int main()
{
    while(scanf("%d" , &n) && n)
    {
        init();
        int i , j , x , y;
        for(i = 1; i <= n; i++)
        {
            for(; ;)
            {
                scanf("%d" , &x);
                if(x == 0)  break;
                scanf("%d" , &y);
                if(grap[i][x] == -1 || grap[i][x] > y)
                    grap[i][x] = y;
            }
        }
        x = match();
        if(x == -1)
        {
            cout<<"N"<<endl;
        }
        else
        {
            x = 0;
            for(i = 1; i <= n; i++)
                x += cx[i];
            cout<<x<<endl;
        }
    }
    return 0;
}


联系
我们