Cyclic Tour （hdu 1853 二分图最小权问题）

Cyclic Tour

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/65535 K (Java/Others)
Total Submission(s): 1883 Accepted Submission(s): 941

Problem Description

There are N cities in our country, and M one-way roads connecting them. Now Little Tom wants to make several cyclic tours, which satisfy that, each cycle contain at least two cities, and each city belongs to one cycle exactly. Tom wants the total length of all the tours minimum, but he is too lazy to calculate. Can you help him?

Input

There are several test cases in the input. You should process to the end of file (EOF).
The first line of each test case contains two integers N (N ≤ 100) and M, indicating the number of cities and the number of roads. The M lines followed, each of them contains three numbers A, B, and C, indicating that there is a road from city A to city B, whose length is C. (1 ≤ A,B ≤ N, A ≠ B, 1 ≤ C ≤ 1000).

Output

Output one number for each test case, indicating the minimum length of all the tours. If there are no such tours, output -1.

Sample Input

Sample Output

42
-1


Hint
 In the first sample, there are two cycles, (1->2->3->1) and (6->5->4->6) whose length is 20 + 22 = 42.

Author

RoBa@TJU

Source

HDU 2007 Programming Contest - Final

Recommend

lcy | We have carefully selected several similar problems for you: 3395 3315 1565 2448 3376

题意：给出n个城市和m条路，有向图，现在Tom想游遍这n个城市，满足路线是若干个回路，要求每个城市要在一个回路中，每条边有一定的旅游花费，问Tom游遍所有城市的最小旅游花费。

思路：二分图最小权问题，把边权取反，用KM算法。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 1005
#define MAXN 2005
#define mod 1000000009
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define FRE(i,a,b)  for(i = a; i <= b; i++)
#define FREE(i,a,b) for(i = a; i >= b; i--)
#define FRL(i,a,b)  for(i = a; i < b; i++)
#define FRLL(i,a,b) for(i = a; i > b; i--)
#define mem(t, v)   memset ((t) , v, sizeof(t))
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf          printf
#define DBG         pf("Hi\n")
typedef long long ll;
using namespace std;

/*
KM算法 O(nx*nx*ny)
求最大权匹配（最佳匹配）
若求最小权匹配，可将权值取相反数，结果取相反数
点的标号从0开始
*/

const int N=110;
int nx,ny;      //两边的点数
int g[N][N];    //二分图描述,g赋初值为-INF
int linker[N],lx[N],ly[N];  //y 中各点匹配状态，x，y中的点的标号
int slack[N];
bool visx[N],visy[N];
bool flag;

bool DFS(int x)
{
    visx[x]=true;
    for (int y=0;y<ny;y++)
    {
        if (visy[y]) continue;
        int tmp=lx[x]+ly[y]-g[x][y];
        if (tmp==0)
        {
            visy[y]=true;
            if (linker[y]==-1||DFS(linker[y]))
            {
                linker[y]=x;
                return true;
            }
        }
        else if (slack[y]>tmp)
            slack[y]=tmp;
    }
    return false;
}

int KM()
{
    flag=true;
    memset(linker,-1,sizeof(linker));
    memset(ly,0,sizeof(ly));
    for (int i=0;i<nx;i++) //赋初值，lx置为最大值
    {
        lx[i]=-INF;
        for (int j=0;j<ny;j++)
        {
            if (g[i][j]>lx[i])
                lx[i]=g[i][j];
        }
    }
    for (int x=0;x<nx;x++)
    {
        for (int i=0;i<ny;i++)
            slack[i]=INF;
        while (true)
        {
            memset(visx,false,sizeof(visx));
            memset(visy,false,sizeof(visy));
            if (DFS(x)) break;
            int d=INF;
            for (int i=0;i<ny;i++)
                if (!visy[i]&&d>slack[i])
                    d=slack[i];
            for (int i=0;i<nx;i++)
                if (visx[i])
                    lx[i]-=d;
            for (int i=0;i<ny;i++)
            {
                if (visy[i])
                    ly[i]+=d;
                else
                    slack[i]-=d;
            }
        }
    }
    int res=0;
    for (int i=0;i<ny;i++)
    {
        if (linker[i]==-1||g[linker[i]][i]<=-INF) //有的点不能匹配的话return-1
        {
            flag=false;
            break;
        }
        res+=g[linker[i]][i];
    }
    return res;
}

int n,m;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("C:/Users/asus1/Desktop/IN.txt","r",stdin);
#endif
    int i,j;
    while (~sff(n,m))
    {
        for (i=0;i<=n;i++)
            for (j=0;j<=n;j++)
                g[i][j]=-INF;
        nx=ny=n;
        int u,v,w;
        for (i=0;i<m;i++)
        {
            sfff(u,v,w);
            u--;
            v--;
            if (-w>g[u][v])
                g[u][v]=-w;
        }
        int ans=KM();
        ans=-ans;
        if (!flag)
            pf("-1\n");
        else
            pf("%d\n",ans);
    }
    return 0;
}

Cyclic Tour （hdu 1853 二分图最小权有关问题）

Cyclic Tour

相关推荐