【最小割->最短路】BZOJ1001(BeiJing2006)[狼抓兔子]題解

題目概述

給出一張網格圖，兔子從(1,1)逃向(n,m)，有橫向道路，縱向道路和對角線道路，每條道路都有一個流量限制（即最多能通過多少兔子），一隻狼隻能抓一隻兔子。問最多在邊上放置多少隻狼才能完全堵截兔子。

解題報告

一道神奇的題目。一眼看去果斷最小割（求最大流），然而n和m巨大，足以讓你爆炸。是以要另辟蹊徑。

這道題的最小割肯定是從左或下割到右或上，但是由于這是網格圖，割過去肯定會經過題目給出的那些邊，求最小割的話隻需要經過邊的權值總和最小即可。

等等，經過權值總和最小？這不就是最短路嗎？是以這道題就轉化為：把每條邊當成點，網格圖中每個三角形中的點互相建邊，最後求最短路。

于是果斷開始寫dij+heap，然後竟然完美的逾時了！想了一下發現這道題邊還是挺多的，不是太适合dij+heap(大佬可無視)，删光重寫spfa，然後終于過了。

示例程式

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=,maxe=;

int r,c,E,len_s,dis[maxn+],num[maxn+],que[maxn+];
int lnk[maxn+],son[maxe+],nxt[maxe+];
bool vis[maxn+];

bool Eoln(char ch) {return ch==||ch==||ch==EOF;}
int readi(int &x) //讀入優化
{
    int tot=,f=;char ch=getchar(),lst=' ';
    while ('9'<ch||ch<'0') {if (ch==EOF) return EOF;lst=ch;ch=getchar();}
    if (lst=='-') f=-f;
    while ('0'<=ch&&ch<='9') tot=tot*+ch-,ch=getchar();
    x=tot*f;
    return Eoln(ch);
}
int get_id(int t,int x,int y) //得到道路種類為t，在x,y上的邊的編号
{
    if (t==) return (x-)*(c-)+y; else //橫向邊
    if (t==) return r*(c-)+(x-)*c+y; else //縱向邊
    return r*(c-)+(r-)*c+(x-)*(c-)+y; //對角線邊
}
void Add(int x,int y) {son[++E]=y;nxt[E]=lnk[x];lnk[x]=E;}
int Spfa()
{
    memset(dis,,sizeof(dis));
    int Head=,Tail=;
    for (int j=;j<=c-;j++) {int id=get_id(,r,j);dis[id]=num[id];que[++Tail]=id;vis[id]=true;} //最下面的點
    for (int i=;i<=r-;i++) {int id=get_id(,i,);dis[id]=num[id];que[++Tail]=id;vis[id]=true;} //最左邊的點
    while (Head!=Tail)
    {
        int x=que[Head=(Head+)%maxn];vis[x]=false;
        for (int j=lnk[x];j;j=nxt[j])
            if (dis[x]+num[son[j]]<dis[son[j]])
            {
                dis[son[j]]=dis[x]+num[son[j]];
                if (!vis[son[j]])
                {
                    vis[son[j]]=true;que[Tail=(Tail+)%maxn]=son[j];
                    if (dis[que[(Head+)%maxn]]>dis[que[Tail]]) swap(que[(Head+)%maxn],que[Tail]);
                }
            }
    }
    int ans=dis[];
    for (int j=;j<=c-;j++) ans=min(ans,dis[get_id(,,j)]); //最上面的點
    for (int i=;i<=r-;i++) ans=min(ans,dis[get_id(,i,c)]); //最右邊的點
    return ans;
}
int main()
{
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    readi(r);readi(c);if (r==&&c==) {printf("0\n");return ;}
    for (int i=;i<=r;i++)
    for (int j=;j<=c-;j++)
        readi(num[get_id(,i,j)]);
    for (int i=;i<=r-;i++)
    for (int j=;j<=c;j++)
        readi(num[get_id(,i,j)]);
    for (int i=;i<=r-;i++)
    for (int j=;j<=c-;j++)
        readi(num[get_id(,i,j)]);
    for (int i=;i<=r;i++)
    for (int j=;j<=c-;j++)
    {
        Add(get_id(,i,j),get_id(,i-,j));
        Add(get_id(,i,j),get_id(,i-,j));
    }
    for (int i=;i<=r-;i++)
    for (int j=;j<=c-;j++)
    {
        Add(get_id(,i,j),get_id(,i+,j));
        Add(get_id(,i,j),get_id(,i,j));
    }
    for (int i=;i<=r-;i++)
    for (int j=;j<=c-;j++)
    {
        Add(get_id(,i,j),get_id(,i+,j));
        Add(get_id(,i,j),get_id(,i,j));
    }
    //以上為格子中左下角的三角形之間的建邊
    for (int i=;i<=r-;i++)
    for (int j=;j<=c-;j++)
    {
        Add(get_id(,i,j),get_id(,i,j+));
        Add(get_id(,i,j),get_id(,i,j));
    }
    for (int i=;i<=r-;i++)
    for (int j=;j<=c;j++)
    {
        Add(get_id(,i,j),get_id(,i,j-));
        Add(get_id(,i,j),get_id(,i,j-));
    }
    for (int i=;i<=r-;i++)
    for (int j=;j<=c-;j++)
    {
        Add(get_id(,i,j),get_id(,i,j));
        Add(get_id(,i,j),get_id(,i,j+));
    }
    //以上為格子中右上角的三角形之間的建邊
    printf("%d\n",Spfa());
    return ;
}