uva1376-Animal Run(最小割+对偶图+最短路)

title: uva1376-Animal Run(最小割+对偶图+最短路)
date: 2019-06-04 16:27:49
categories: ACM
tags: [ACM,算法]

我图论好菜啊
我的个人博客：https://www.kimiye.xyz

题目描述

动物园动物要逃跑了，在每个路口有3条路可以走（横、竖、斜），现在给出每条路上警察需要派w个人就能堵住这条路，问最少需要派出多少人可以防止动物走到终点？
起点：左上角
终点：右下角

解题思路

显然从图的左下部分画一条穿过若干边的线到右上部分，图就被分成了2部分，把穿过的边的权值之和加起来就是候选答案，那么这就是一道最小割问题，但由于边数过多不能跑一个最大流，然而这是一个对偶图，可以将最大流转化为最短路求解，使用dijkstra优先队列优化的方法就能快速求解了。。。

代码：

#include <bits/stdc++.h>
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int maxn = 2e6+7;
const int inf = 0x3f3f3f3f;
struct qnode
{
	int v;
	int c;
	qnode(int _v=0,int _c=0):v(_v),c(_c){}
	bool operator <(const qnode &r)const
	{
		return c>r.c;
	}
};
struct Edge
{
	int v,cost;
	Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
int n,m,kase;
vector<Edge> E[maxn];
bool vis[maxn];
int dist[maxn];

void Dijkstra(int n,int start)//点的编号从1开始
{
	memset(vis,false,sizeof(vis));
	for(int i=1;i<=n;i++) dist[i]=inf;
	priority_queue<qnode>que;
	while(!que.empty()) que.pop();
	dist[start]=0;
	que.push(qnode(start,0));
	qnode tmp;
	while(!que.empty())
	{
		tmp=que.top();
		que.pop();
		int u=tmp.v;
		if(vis[u]) continue;
		vis[u]=true;
		for(int i=0;i<E[u].size();i++)
		{
			int v=E[u][i].v;
			int cost=E[u][i].cost;
			if(!vis[v]&&dist[v]>dist[u]+cost)
			{
				dist[v]=dist[u]+cost;
				que.push(qnode(v,dist[v]));
			}
		}
	}
}

void addedge(int u,int v,int w)
{
	E[u].push_back(Edge(v,w));
}
int main()
{
    while(scanf("%d %d",&n,&m)!=EOF && n+m)
    {
        int s=2*(n-1)*(m-1)+2;
        int t=2*(n-1)*(m-1)+1;
        int u,v,w;
        for(int i=1;i<=s;i++)
            E[i].clear();
        // 横线
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m-1;j++)
            {
                scanf("%d",&w);
                if(i==1)
                {
                    u=2*j;
                    addedge(t,u,w);
                    addedge(u,t,w);
                }
                else if(i==n)
                {
                    u=2*(n-2)*(m-1)+2*(j-1)+1;
                    addedge(s,u,w);
                    addedge(u,s,w);
                }
                else
                {
                    // 跟下边的格子
                    u=2*(i-2)*(m-1)+2*(j-1)+1;
                    v=u+2*(m-1)+1;
                    addedge(u,v,w);
                    addedge(v,u,w);
                }
            }
        // 竖线
        for(int i=1;i<=n-1;i++)
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&w);
                if(j==1)
                {
                    u=2*(i-1)*(m-1)+1;
                    addedge(s,u,w);
                    addedge(u,s,w);
                }
                else if(j==m)
                {
                    u=2*i*(m-1);
                    addedge(t,u,w);
                    addedge(u,t,w);
                }
                else
                {
                    // 跟右边的格子
                    u=2*(i-1)*(m-1)+2*(j-1);
                    v=u+1;
                    addedge(u,v,w);
                    addedge(v,u,w);
                }
            }
        // 斜线
        for(int i=1;i<=n-1;i++)
            for(int j=1;j<=m-1;j++)
            {
                // 跟上面的格子
                scanf("%d",&w);
                u=2*(i-1)*(m-1)+2*j-1;
                v=u+1;
                addedge(u,v,w);
                addedge(v,u,w);
            }
        Dijkstra(s,s);
        printf("Case %d: Minimum = %d\n",++kase,dist[t]);
    }
    return 0;
}