首页 > 代码库 > BZOJ 1266 AHOI 2006 上学路线route 最小割
BZOJ 1266 AHOI 2006 上学路线route 最小割
题目大意:给出一个无向图,问从1到n的最短路发生变化需要割掉最少花费的边权总值是多少。
思路:先要把所有最短路上的边搞出来,一个Floyd就可以解决,然后把所有在最短路上的边都加到最大流的图中,然后跑最小割就是答案。
CODE:
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 510 #define MAXE 300000 #define INF 0x3f3f3f3f #define S 1 #define T points using namespace std; #define min(a,b) ((a) < (b) ? (a):(b)) struct Edge{ int x,y,len; int cost; Edge(int _,int __,int ___,int ____):x(_),y(__),len(___),cost(____) {} Edge() {} }edge[MAXE]; int points,edges; int map[MAX][MAX]; struct MaxFlow{ int head[MAX],total; int _next[MAXE << 1],aim[MAXE << 1],flow[MAXE << 1]; int f[MAX],deep[MAX]; bool v[MAX]; MaxFlow() { total = 1; memset(head,0,sizeof(head)); } void Add(int x,int y,int f) { _next[++total] = head[x]; aim[total] = y; flow[total] = f; head[x] = total; } void Insert(int x,int y,int f) { Add(x,y,f); Add(y,x,0); } bool BFS() { static queue<int> q; while(!q.empty()) q.pop(); memset(f,0x3f,sizeof(f)); memset(deep,0,sizeof(deep)); deep[S] = 1; f[S] = 0; q.push(S); while(!q.empty()) { int x = q.front(); q.pop(); v[x] = false; for(int i = head[x]; i; i = _next[i]) if(!deep[aim[i]] && flow[i]) { deep[aim[i]] = deep[x] + 1; q.push(aim[i]); if(aim[i] == T) return true; } } return false; } int Dinic(int x,int f) { if(x == T) return f; int temp = f; for(int i = head[x]; i; i = _next[i]) if(flow[i] && deep[aim[i]] == deep[x] + 1 && temp) { int away = Dinic(aim[i],min(flow[i],temp)); if(!away) deep[aim[i]] = 0; flow[i] -= away; flow[i^1] += away; temp -= away; } return f - temp; } }solver; int main() { cin >> points >> edges; memset(map,0x3f,sizeof(map)); for(int i = 1; i <= points; ++i) map[i][i] = 0; for(int x,y,z,t,i = 1; i <= edges; ++i) { scanf("%d%d%d%d",&x,&y,&z,&t); map[x][y] = map[y][x] = z; edge[i] = Edge(x,y,z,t); } for(int k = 1; k <= points; ++k) for(int i = 1; i <= points; ++i) for(int j = 1; j <= points; ++j) map[i][j] = min(map[i][j],map[i][k] + map[k][j]); cout << map[1][points] << endl; for(int i = 1; i <= edges; ++i) { if(map[1][edge[i].x] + map[edge[i].y][points] + edge[i].len == map[1][points]) solver.Insert(edge[i].x,edge[i].y,edge[i].cost); if(map[1][edge[i].y] + map[edge[i].x][points] + edge[i].len == map[1][points]) solver.Insert(edge[i].y,edge[i].x,edge[i].cost); } int max_flow = 0; while(solver.BFS()) max_flow += solver.Dinic(S,INF); cout << max_flow << endl; return 0; }
BZOJ 1266 AHOI 2006 上学路线route 最小割
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。