广州市品牌网站建设公司,西安百度推广开户,虹口北京网站建设,留白的网站正题
题目链接:https://www.luogu.com.cn/problem/P4300 题目大意 nnn个点mmm条边的无向图。求1∼n1\sim n1∼n的最短路和删除cic_ici和最小的边使得最短路变长。 解题思路
显然我们需要跑一次最短路。
之后考虑如何求第二问#xff0c;我们发现我们要割掉最短路上的边我们发现我们要割掉最短路上的边所以我们只要把最短路树一张有最短路上的边构成的DAGDAGDAG构出来然后在上面求最小割就好了。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int N510,inf2147483647/3;
struct edge_node{int x,y,w,c;
}e[124760];
struct point{int pos,val;
};
struct node{int to,next,w;
}a[124760*2];
bool operator(point x,point y)
{return x.valy.val;}
int n,m,s,t,tot,f[N],ls[N],dep[N],ans;
bool v[N];queueint qq;
priority_queuepoint q;
void addl(int x,int y,int w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;return;
}
void dij(){memset(f,0x3f,sizeof(f));q.push((point){1,0});f[1]0;while(!q.empty()){int xq.top().pos;q.pop();if(v[x])continue;v[x]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(f[x]a[i].wf[y]){f[y]f[x]a[i].w;if(!v[y])q.push((point){y,f[y]});}}}return;
}
bool bfs(){while(!qq.empty())qq.pop();qq.push(1);memset(dep,0,sizeof(dep));dep[s]s;while(!qq.empty()){int xqq.front();qq.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(dep[y]||!a[i].w)continue;dep[y]dep[x]1;if(yt)return 1;qq.push(y);}}return 0;
}
int dinic(int x,int flow){if(xt)return flow;int rest0,k;for(int ils[x];i;ia[i].next){int ya[i].to;if(dep[x]1!dep[y]||!a[i].w)continue;rest(kdinic(y,min(a[i].w,flow-rest)));a[i].w-k;a[i^1].wk;if(flowrest)return flow;}if(!rest)dep[x]0;return rest;
}
void dfs(int x,int fa){v[x]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(f[y]a[i].wf[x])if(!v[y])dfs(y,x);}
}
int main()
{scanf(%d%d,n,m);s1;tn;for(int i1;im;i){scanf(%d%d%d%d,e[i].x,e[i].y,e[i].w,e[i].c);addl(e[i].x,e[i].y,e[i].w);addl(e[i].y,e[i].x,e[i].w);}dij();tot1;memset(v,0,sizeof(v));dfs(n,n);memset(ls,0,sizeof(ls));for(int i1;im;i){if(!v[e[i].x]||!v[e[i].y])continue;if(f[e[i].x]e[i].wf[e[i].y]){addl(e[i].x,e[i].y,e[i].c);addl(e[i].y,e[i].x,0);}if(f[e[i].y]e[i].wf[e[i].x]){addl(e[i].x,e[i].y,0);addl(e[i].y,e[i].x,e[i].c);}}while(bfs())ansdinic(s,inf);printf(%d\n%d\n,f[n],ans);
}
