752. [BJOI2006] 狼抓兔子

★★★ 输入文件：bjrabbit.in 输出文件：bjrabbit.out 简单对比
时间限制：1 s 内存限制：162 MB

Description Source: Beijing2006 [BJOI2006]

八中OJ上本题链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1001

现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到，但抓兔子还是比较在行的，而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：

左上角点为(1,1),右下角点为(N,M)(上图中N=4,M=5).有以下三种类型的道路 1:(x,y)<==>(x+1,y) 2:(x,y)<==>(x,y+1) 3:(x,y)<==>(x+1,y+1) 道路上的权值表示这条路上最多能够通过的兔子数，道路是无向的. 左上角和右下角为兔子的两个窝，开始时所有的兔子都聚集在左上角(1,1)的窝里，现在它们要跑到右下解(N,M)的窝中去，狼王开始伏击这些兔子.当然为了保险起见，如果一条道路上最多通过的兔子数为K，狼王需要安排同样数量的K只狼，才能完全封锁这条道路，你需要帮助狼王安排一个伏击方案，使得在将兔子一网打尽的前提下，参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦.

Input

第一行为N,M.表示网格的大小，N,M均小于等于1000.接下来分三部分第一部分共N行，每行M-1个数，表示横向道路的权值. 第二部分共N-1行，每行M个数，表示纵向道路的权值. 第三部分共N-1行，每行M-1个数，表示斜向道路的权值. 输入文件保证不超过10M

Output

输出一个整数，表示参与伏击的狼的最小数量.

Sample Input

3 4
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6

Sample Output

如果你想到了一个定理：

最大流==最小割，

然后聪明的想到了Dinic跑最大流

那么恭喜你，

被坑了，。。，

因为这道题的数据范围比较大

Dinic肯定跑步过去，

所以考虑用对偶图跑最短路，

至于为什么，，，我也不太懂，，

特别是代码。。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #define inf 0x7fffffff

 using namespace std;

 const int maxn=+;

 const int M = maxn*+;

 int n,m,nn,mm;

 int from,to;

 struct Edge

 {

     int v,flow;

     int next;

 }edge[M];

 int head[maxn],edgenum;

 void add(int u,int v,int flow)

 {

     edge[edgenum].v=v ;edge[edgenum].flow=flow ;

     edge[edgenum].next=head[u] ;head[u]=edgenum++ ;

     edge[edgenum].v=u ;edge[edgenum].flow=flow ;

     edge[edgenum].next=head[v] ;head[v]=edgenum++ ;

 }

 struct node

 {

     int v,w;

     friend bool operator < (node a,node b)

     {

         return a.w > b.w;

     }

 }cur,tail;

 int d[maxn],vis[maxn];

 void Dijkstra(int from,int to)

 {

     for (int i= ;i<maxn ;i++) d[i]=inf;

     memset(vis,,sizeof(vis));

     d[from]=;

     priority_queue<node> Q;

     cur.v=from ;cur.w= ;

     Q.push(cur);

     while (!Q.empty())

     {

         cur=Q.top() ;Q.pop() ;

         int x=cur.v;

         if (vis[x]) continue;

         vis[x]=;

         for (int i=head[x] ;i!=- ;i=edge[i].next)

         {

             if (d[edge[i].v ]>d[x]+edge[i].flow)

             {

                 d[edge[i].v ]=d[x]+edge[i].flow;

                 tail.v=edge[i].v;

                 tail.w=d[edge[i].v ];

                 Q.push(tail);

             }

         }

     }

     printf("%d\n",d[to]);

 }

 int main()

 {

     while (scanf("%d%d",&n,&m)!=EOF)

     {

         memset(head,-,sizeof(head));

         edgenum=;

         from=;

         to=*(n-)*(m-)+;

         int x,y,cost;

         for (int i= ;i<=n ;i++)

         {

             for (int j= ;j<m ;j++)

             {

                 scanf("%d",&cost);

                 x= i== ? from : (*(i-)-)*(m-)+j;

                 y= i==n ? to : (*(i-))*(m-)+j;

                 add(x,y,cost);

             }

         }

         for (int i= ;i<n ;i++)

         {

             for (int j= ;j<=m ;j++)

             {

                 scanf("%d",&cost);

                 x= j== ? to : (*(i-))*(m-)+j-;

                 y= j==m ? from : (*(i-))*(m-)+j-+m;

                 add(x,y,cost);

             }

         }

         for (int i= ;i<n ;i++)

         {

             for (int j= ;j<m ;j++)

             {

                 scanf("%d",&cost);

                 x=(*(i-))*(m-)+j;

                 y=(*(i-)+)*(m-)+j;

                 add(x,y,cost);

             }

         }

         Dijkstra(from,to);

     }

     return ;

 }

下面是自己写的蜜汁WA、、

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<queue>

 #include<algorithm>

 using namespace std;

 const int MAXN=;

 const int MAXM=;

 const int maxn=0x7fffffff;

 inline void read(int &n)

 {

     char c='+';int x=;bool flag=;

     while(c<''||c>''){c=getchar();if(c=='-')flag=;}

     while(c>=''&&c<=''){x=x*+(c-);c=getchar();}

     flag==?n=-x:n=x;

 }

 struct node

 {

     int u,v,f,nxt;

 }edge[MAXM];

 int head[MAXN];

 int num=;

 int n,m;

 int dis[MAXN];

 bool vis[MAXN];

 inline void add_edge(int x,int y,int z)

 {

     edge[num].u=x;

     edge[num].v=y;

     edge[num].f=z;

     edge[num].nxt=head[x];

     head[x]=num++;

 }

 inline void SPFA(int s,int t)

 {

     for(int i=;i<t;i++)

         dis[i]=maxn;

     dis[s]=;

     vis[s]=;

     queue<int>q;

     q.push(s);

     while(q.size()!=)

     {

         int p=q.front();

         q.pop();

         vis[p]=;

         for(int i=head[p];i!=-;i=edge[i].nxt)

         {

             if(dis[edge[i].v]>dis[edge[i].u]+edge[i].f)

             {

                 dis[edge[i].v]=dis[edge[i].u]+edge[i].f;

                 if(vis[edge[i].v]==)

                 {

                     vis[edge[i].v]=;

                     q.push(edge[i].v);

                 }

             }

         }

     }

     printf("%d",dis[t]);

 }

 int main()

 {

     //freopen("bjrabbit.in","r",stdin);

     //freopen("bjrabbit.out","w",stdout);

     read(n);read(m);

     memset(head,-,sizeof(head));

     int from=;

     int to=(*(n-)*(m-))+;

     int spend,x,y;

     for(int i=;i<=n;i++)

         for(int j=;j<m;j++)

         {

             read(spend);

             x= i==? from: (*(i-)-)*(m-)+j;

             y= i==n? to : (*(i-))*(m-)+j;

         //    printf("%d %d %d \n",x,y,spend);

             add_edge(x,y,spend);

             add_edge(y,x,spend);

         }

     for(int i=;i<n;i++)

         for(int j=;j<=m;j++)

         {

             read(spend);

             x= j==?to:(*(i-))*(m-)+j-;

             y= j==m?from:(*(i-))*(m-)+j-+m;

             //printf("%d %d %d \n",x,y,spend);

             add_edge(x,y,spend);

             add_edge(y,x,spend);

         }

     for(int i=;i<n;i++)

         for(int j=;j<m;j++)

         {

             read(spend);

             x=(*(i-))*(m-)+j;

             y=(*(i-)+)*(m-)+j;

             //printf("%d %d %d \n",x,y,spend);

             add_edge(x,y,spend);

             add_edge(y,x,spend);

         }

     SPFA(from,to);

     return ;

 }

巴特西