UVA 1349Optimal Bus Route Design（二分圖最小權完美比對+拆點）

題目連結

題目大意：有這麼n個經典，需要指定若幹個旅遊路線，要求這些路由路線從起點出發後還要再回到起點，且所有路線覆寫全部景點，一個景點最多被一個路線覆寫，要求路線的權值和最小并輸出，無解輸出N

分析：從起點回到起點，這明顯是一個圈，要求若幹個圈且每個點都恰好屬于一個圈，也就是說每個點都有唯一一個後繼結點，從後繼節點又有後繼結點，也就是說每個點都恰好和他的後繼結點有一條邊相連，而他的後繼結點還要和他的後繼節點有邊相連，也就是說每個點都會恰好選擇一個點作為他的後繼結點，每個點也都會恰好被一個點選作後繼結點，每個點隻有選擇和被選兩種狀态，是以把每個點拆成X和Y兩個點，X代表從X出發，Y代表被選作後繼結點，比如若有邊 u − > v u->v u−>v則對應邊 X u − > Y v X_u->Y_v Xu​−>Yv​這是一個二分圖，題目要求每個點都恰好在圈中，則要求是一個二分圖的完美比對，是以我們直接跑費用流，最後判斷是否滿流即可。

#include<bits/stdc++.h>
#define PII pair<int,int>
#define x first
#define y second
#define MAIN main
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N=2e3+100;
int n;
struct edge
{
    int u,v,cap,flow,cost;
    edge(int u=0,int v=0,int cap=0,int flow=0,int cost=0):u(u),v(v),cap(cap),flow(flow),cost(cost){}
};
vector<edge>E;
vector<int>g[N];
void add(int u,int v,int cap,int cost)
{
    E.push_back(edge(u,v,cap,0,cost));
    E.push_back(edge(v,u,0,0,-cost));
    int m=E.size();
    g[u].push_back(m-2);
    g[v].push_back(m-1);
}
int dis[N],vis[N],pre[N],a[N];
bool SPFA(int s,int t,int &flow,int &cost)
{
    memset(vis,0,sizeof(vis));
    for(int i=0;i<=2*n+1;i++) dis[i]=INF;
    a[s]=INF;pre[s]=0;dis[s]=0;vis[s]=1;
    queue<int>q;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=0;i<(int)g[u].size();i++)
        {
            edge &e=E[g[u][i]];
            int v=e.v;
            if(e.cap>e.flow&&dis[v]>dis[u]+e.cost)
            {
                dis[v]=dis[u]+e.cost;
                pre[v]=g[u][i];
                a[v]=min(a[u],e.cap-e.flow);
                if(!vis[v]) vis[v]=1,q.push(v);
            }
        }
    }
    if(dis[t]==INF) return false;
    flow+=a[t];
    cost+=dis[t]*a[t];
    int u=t;
    while(u!=s)
    {
        E[pre[u]].flow+=a[t];
        E[pre[u]^1].flow-=a[t];
        u=E[pre[u]].u;
    }
    return true;
}
int mincost(int s,int t,int &flow)
{
    int cost=0;
    while(SPFA(s,t,flow,cost));
    return cost;
}
int MAIN()
{
    while(scanf("%d",&n)==1)
    {
        if(n==0) break;
        int s=0,t=2*n+1;
        E.clear();
        for(int i=s;i<=t;i++) g[i].clear();
        for(int i=1;i<=n;i++)
        {
            int v,w;
            while(scanf("%d",&v)==1)
            {
                if(v==0) break;
                scanf("%d",&w);
                add(i,v+n,1,w);
            }
        }
        for(int i=1;i<=n;i++){
            add(s,i,1,0);
            add(i+n,t,1,0);
        }
        int flow=0;
        int ans=mincost(s,t,flow);
        if(flow==n) printf("%d\n",ans);
        else puts("N");
    }
    return 0;
}