题解 P4001 【[ICPC-Beijing 2006]狼抓兔子】

~~玄学$dinic$居然不会被卡~~ 首先讲讲对偶图，首先对于这样一张图  它的对偶图就是(忽略原来的那9个点)  我们可以把这个对偶图理解为插孔？对偶图的某一边边权就是那条边所交叉的原图的边权。比如上图$W_{0->17}=W_{1->4}=5$ 然后我们就可以用对偶图来维护连通性的问题啦！ 先来一道水题（不知道哪来的） 请您维护一张$n*n(n\leq1000)$的网格图(没有边权)，初始所有边都在，就像这样  > 这是一张 $3*3$ 的网格图 之后有$m(m\leq100000)$个操作，割去$(x_1,y_1)$到$(x_2,y_2)$的边，保证不会割去重复的边 初始整张图是一个联通块，对于每一次操作，如果使联通块的数量变多了，请输出它是第几个操作。 读完题，发现蒟蒻我不会删边，于是就用到对偶图这个东西。 上文我们提到 > 对偶图的某一边边权就是那条边所交叉的原图的边权 我们不妨把对偶图的边权理解成割掉原图的边的代价（似乎变成最小割=.=了），于是我们通过**维护对偶图的连通性，反而可以得出原图的不连通性**。 然后维护连通性用并查集就好了，如果$findfa(x1,y1)==findfa(x2,x2)$,那就$ans++$（因为题目保证了保证不会割去重复边） 好了，知道了这些知识就可以秒了这道题了 把左下 和 右上分开，dijkstra求左下到右上的最短路 **维护对偶图的最短路，反而可以得出原图的最小割** 对于题目样例  建一个这样的图，跑dij就行了  只是对偶图建图有点恶心 请自己思考一下怎么转对偶图吧……我是解释不清 ``` //本篇代码以(n,m)为原点 (n+1,m+1)为终点 #include<cstdio> #include<cstring> #include<ctime> #include<algorithm> #include<queue> #define rg register #define MAXN (2000+10) int head[MAXN][MAXN],tot; struct edge{ int next,x,y,w; }h[MAXN*MAXN*2*2]; inline void addedge(int x,int y,int x1,int y1,int w){ //建边 h[++tot].next = head[x][y]; head[x][y] = tot; h[tot].x = x1, h[tot].y = y1; h[tot].w = w; } struct node{ int x,y,w; bool operator < (const node b) const{ return b.w<w; } }; int n,m; bool vis[MAXN][MAXN]; int dis[MAXN][MAXN]; void dij(int stx,int sty){//最短路 memset(dis,0x3f,sizeof(dis)); std::priority_queue<node> q; dis[stx][sty] = 0; q.push((node){stx , sty , 0}); while(!q.empty()){ node now = q.top(); q.pop(); int x = now.x,y = now.y; //printf("%d %d \n",x,y); if(vis[x][y]) continue; vis[x][y] = 1; for(rg int i = head[x][y] ; i ; i = h[i].next){ int tox = h[i].x,toy = h[i].y,w = h[i].w; //printf("trying %d %d dis = %d \n",tox,toy,dis[tox][toy]); if(dis[x][y] + w < dis[tox][toy]){ dis[tox][toy] = dis[x][y] + w; //printf("CHange dis[%d][%d]=%d \n",tox,toy,dis[tox][toy]); if(!vis[tox][toy]) q.push((node){tox,toy,dis[tox][toy]}); } } } return ; } int main(){ scanf("%d%d",&n,&m); if(n==1){ int ans=1<<30; for(rg int i = 1 , w;i < m ; ++i){ scanf("%d",&w); if(w < ans) ans = w; } printf("%d \n",ans); return 0; } if(m == 1){ int ans=1<<30; for(rg int i = 1 , w;i < n ; ++i){ scanf("%d",&w); if(w < ans) ans = w; } printf("%d \n",ans); return 0; } for(rg int i = 1 ,w; i <= n ; ++i){ for(rg int j = 1 ; j < m ; ++j){//此后毒瘤建图 scanf("%d",&w); if(i == 1){ addedge(i,j<<1,n+1,m+1,w); addedge(n+1,m+1,i,j<<1,w); } else if(i == n){ addedge(i-1,(j<<1)-1,n,m,w); addedge(n,m,i-1,(j<<1)-1,w); } else{ addedge(i-1,(j<<1)-1,i,j<<1,w); addedge(i,j<<1,i-1,(j<<1)-1,w); } } } for(rg int i = 1,w ; i < n ; ++i){ for(rg int j = 1 ; j <= m ;++j){ scanf("%d",&w); if(j == 1){ addedge(n,m,i,(j<<1)-1,w); addedge(i,(j<<1)-1,n,m,w); } else if(j == m){ addedge(n+1,m+1,i,(m-1)<<1,w); addedge(i,(m-1)<<1,n+1,m+1,w); } else{ addedge(i,(j-1)<<1,i,(j-1)<<1|1,w); addedge(i,(j-1)<<1|1,i,(j-1)<<1,w); } } } for(rg int i = 1,w; i < n ;i++){ for(rg int j = 1; j < m ; ++j){ scanf("%d",&w); addedge(i,(j<<1)-1,i,j<<1,w); addedge(i,j<<1,i,(j<<1)-1,w); } } dij(n,m); printf("%d \n",dis[n+1][m+1]); return 0; } ```