HITOJ 2739 The Chinese Postman Problem(帯権図の中国郵便配達員問題あり)

The Chinese Postman Problem Source : bin3 Time limit : 1 sec Memory limit : 64 M Submitted : 530, Accepted : 177 A Chinese postman is assigned to a small town in China to deliver letters. In this town, each street is oriented and connects exactly two junctions. The postman’s task is to start at the post office and pass each street at least once to deliver letters. At last, he must return to the post office. Can you help him to make sure whether there exist feasible routes for him and find the minimum distance from all the feasible routes. Input Input contains multiple test cases. The first line is an integer T, the number of test cases. Each case begins with two integers N, M, with 2 ≤ N ≤ 100, 1 ≤ M ≤ 2000, representing the number of junctions and the number of streets respectively. Then M lines will follow, each denoting a street. A street is represented by three integers u, v, d, with 0 ≤ u, v < N, 0 < d ≤ 1000, meaning this street whose length is d connects the junction u and v and the postman can only travel from junction u to v. Junctions are numbered from 0 to N-1. Junction 0 is always the post office. Note that there may be more than one street connecting the same pair of junctions. Output Output one line for each test case. If there exist feasible routes for the postman, output the minimum distance. Otherwise, output -1. Sample Input 3 2 1 0 1 3 4 4 0 1 1 1 2 2 2 3 3 3 0 4 4 7 0 1 1 1 2 2 2 3 3 3 0 4 1 3 5 3 1 2 1 3 2 Sample Output -1 10 21

テーマ：

任意の点からすべての辺に入ってからこの点に戻る最小費用(何度も歩くことができる)を求めて、帯辺権図をあげます.

問題解決の考え方：

まず,入度または出度が0の点があれば解がないことが分かる.そして、連通しなければ解けない.まず各エッジを1回通過すると,入度が出度に等しくない点の流量にアンバランスが生じ,流量をバランスさせるために,入度より大きいものから入度が出度より大きいものまでの経路をバランスまで追加し続ける.このプロセスは、最小費用最大ストリームによって実現され、費用を最小にすることができる.D(i)をi番ノードの入度から度を減算し、D(i)>0であればiからポイント容量D(i)まで費用が0のエッジ、D(i)<0であればソースポイントi容量−D(i)費用が0のエッジを1つ接続する.原図中の各エッジの始点終点については変わらず,容量は∞費用が原費用である.最小費用の最大流を走って原図のすべての辺を加える権利が答えです.

ACコード

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long
#define fi first
#define se second
#define mem(a,b) memset((a),(b),sizeof(a))

const int MAXV=100+3;
const int MAXE=2000+3;

struct Edge
{
    int to,next,cap,cost;
    Edge(int t=0,int n=0,int ca=0,int f=0,int co=0):to(t),next(n),cap(ca),cost(co){}
}edge[2*(MAXE+MAXV)];

int V, E;
int in[MAXV], out[MAXV];
int head[MAXV],tol;
int pre[MAXV],dis[MAXV];
bool vis[MAXV];

void add_edge(int u,int v,int cap,int cost)
{
    edge[tol]=Edge(v,head[u],cap,0,cost);
    head[u]=tol++;
    edge[tol]=Edge(u,head[v],0,0,-cost);
    head[v]=tol++;
}

bool spfa(int s,int t)
{
    queue<int> que;
    for(int i=0;ifalse;
        pre[i]=-1;
    }
    dis[s]=0;
    vis[s]=true;
    que.push(s);
    while(!que.empty())
    {
        int u=que.front(); que.pop();
        vis[u]=false;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if(edge[i].cap>0&&dis[v]>dis[u]+edge[i].cost)
            {
                dis[v]=dis[u]+edge[i].cost;
                pre[v]=i;
                if(!vis[v])
                {
                    vis[v]=true;
                    que.push(v);
                }
            }
        }
    }
    return pre[t]!=-1;
}

int min_cost_flow(int s,int t,int &cost)//       ，cost       
{
    int flow=0;
    cost=0;
    while(spfa(s,t))
    {
        //      ， spfa   dis[t]>=0       
        int the_min=INF;
        for(int i=pre[t];i!=-1;i=pre[edge[i^1].to])
            the_min=min(the_min, edge[i].cap);
        for(int i=pre[t];i!=-1;i=pre[edge[i^1].to])
        {
            edge[i].cap-=the_min;
            edge[i^1].cap+=the_min;
            cost+=edge[i].cost*the_min;
        }
        flow+=the_min;
    }
    return flow;
}

int par[MAXV], high[MAXV];

int findfather(int x)
{
    return par[x]=par[x]==x?x:findfather(par[x]);
}

bool unite(int a, int b)
{
    int fa=findfather(a), fb=findfather(b);
    if(fa==fb)
        return false;
    if(high[fa]>high[fb])
        par[fb]=fa;
    else
    {
        par[fa]=fb;
        if(high[fa]==high[fb])
            ++high[fb];
    }
    return true;
}

void init()
{
    for(int i=0;i2;++i)
    {
        head[i]=-1;
        par[i]=i;
        high[i]=0;
        in[i]=out[i]=0;
    }
    tol=0;
}

int main()
{
    int T_T;
    scanf("%d", &T_T);
    while(T_T--)
    {
        scanf("%d%d", &V, &E);
        init();
        int sum=0;
        for(int i=0;iint u, v, c;
            scanf("%d%d%d", &u, &v, &c);
            unite(u, v);
            ++out[u];
            ++in[v];
            add_edge(u, v, INF, c);
            sum+=c;
        }
        bool ok=true;
        for(int i=1;iif(findfather(0)!=findfather(i))//     ，   
            {
                ok=false;
                break;
            }
        int s=V, t=V+1;
        for(int i=0;iif(in[i]==0 || out[i]==0)//        0  ，  
            {
                ok=false;
                break;
            }
            if(out[i]-in[i]>0)
                add_edge(i, t, out[i]-in[i], 0);
            else if(out[i]-in[i]<0)
                add_edge(s, i, in[i]-out[i], 0);
        }
        if(!ok)
        {
            puts("-1");
            continue;
        }
        V+=2;
        int ans;
        min_cost_flow(s, t, ans);
        printf("%d
", ans+sum);
    }

    return 0;
}