[bzoj 1001]狼爪兔子

前几天,可能是我记错了谁都没推荐可能是fls推荐也可能是文大爷推荐也可能是这俩人同时推荐我去写bzoj,然后今天我就开始去写了。

写的第一道题是狼爪兔子,题目内容http://www.lydsy.com/JudgeOnline/problem.php?id=1001

看了一眼我感觉是最大流的题目我就找了个dinic的模板开始写

然后超时了。

我以为是板子错了然后改了改又交了一发,还是超时。

后来才学到一个叫做最大最小定理的技巧。大概意思是由于这个图G是一个平面图,所以我们可以做如下处理:建一个新的图G*,其中G*中的顶点为G中的面,G*中边权值定义为G中同时被对应的两个面包含的边的流量。然后再将G中的源点和汇点连一条线,这样我们就可以找到两个新的面,定义其中一个面为起点,另一个面为终点。这样我们只需在G*中找一个最短路,因为这条最短路中,相邻顶点之间的边实际上是切过G中对应的边的,而且边权等于流量,所以走完这个最短路等于在G中找到了一个割,而且很容易看出这个割就是最小割,也就找到了最大流。

详细内容可以看一份PPT:https://wenku.baidu.com/view/8f1fde586edb6f1aff001f7d.html?re=view

然后代码如下:

 

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=2000005;
const int maxm=8000040;
struct edge{
    int from,to,cap,next;
}edge[maxm];
int dis[maxn],que[maxn],head[maxn],flag[maxn],tol=0,n,m,w;
void addedge(int u,int v,int w){
    edge[tol].from=u;
    edge[tol].to=v;
    edge[tol].cap=w;
    edge[tol].next=head[u];
    head[u]=tol++;
    edge[tol].from=v;
    edge[tol].to=u;
    edge[tol].cap=w;
    edge[tol].next=head[v];
    head[v]=tol++;
}
void spfa(){
    memset(dis,inf,sizeof(dis));
    int front=0,rear=0;
    dis[0]=que[rear++]=0,flag[0]=1;
    while(front!=rear){
        int u=que[front++];
        flag[u]=0;
        if(front==maxn)front=0;
        for(int i=head[u];i;i=edge[i].next){
            int v=edge[i].to;
            if(dis[v]>dis[u]+edge[i].cap){
                dis[v]=dis[u]+edge[i].cap;
                if(flag[v]==0){
                    flag[v]=1;
                    que[rear++]=v;
                    if(rear==maxn)rear=0;
                }
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    int end=(n*m+1)<<1;
    int start=0;
    int u,v;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m-1;j++){
            scanf(" %d",&w);
            u=(m-1)*(2*i-3)+j;
            v=(m-1)*(2*i-2)+j;
            if(i==1){
                u=end;
            }
            else if(i==n){
                v=start;
            }
            addedge(u,v,w);
        }
    }
    for(int i=1;i<=n-1;i++){
        int u=(i-1)*m+1;
        for(int j=1;j<=m;j++){
            scanf(" %d",&w);
            u=(m-1)*(i*2-2)+j-1;
            v=(m-1)*(i*2-1)+j;
            if(j==1) u=start;
            if(j==m) v=end;
            addedge(u,v,w);
        }
    }
    for(int i=1;i<=n-1;i++){
        for(int j=1;j<=m-1;j++){
            scanf(" %d",&w);
            u=(m-1)*(i*2-1)+j;
            v=(m-1)*(i*2-2)+j;
            addedge(u,v,w);
        }
    }
    spfa();
    printf("%d\n",dis[end]);
    return 0;
}

发表评论

电子邮件地址不会被公开。

This site uses Akismet to reduce spam. Learn how your comment data is processed.