Codeforces700C. Break Up
2024-08-30 20:53:19
n<=1000,m<=30000的图,问割掉边权和尽量小的0、1或2条边使S和T不连通,输出割了哪些边,无解-1.
道理是很好懂的,先随便找S到T的一条路径,找不到输出0,找到的话这条路上至少有一条边要删,那枚举一下割谁,对剩下的图再做tarjan即可。复杂度(n*m)。
然而!!写起来是很难写的。。
方法一:一开始把所有S到T的路径上的边都标记好,枚举割的第一条边后跑完tarjan,直接看这些边会不会是割边再取min即可。
方法二:枚举割的第一条边后,tarjan求个边双,然后缩起来建树,在树上搜一次。
方法二。
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<vector>
//#include<assert.h>
#include<algorithm>
//#include<iostream>
using namespace std; int n,m,s,t;
#define maxn 1011
#define maxm 60011
struct Edge{int to,v,next;}edge[maxm]; int first[maxn],le=;
void in(int x,int y,int v) {Edge &e=edge[le]; e.to=y; e.v=v; e.next=first[x]; first[x]=le++;}
void insert(int x,int y,int v) {in(x,y,v); in(y,x,v);} int list[maxn],ll=,ans,numofans,whoisans[];
bool vis[maxn];
bool dfs(int x)
{
if (x==t) return ;
vis[x]=;
for (int i=first[x];i;i=edge[i].next)
{
const Edge &e=edge[i]; if (vis[e.to]) continue;
list[++ll]=i>>;
if (dfs(e.to)) return ;
ll--;
}
return ;
} int bel[maxn],tot,Time,low[maxn],dfn[maxn],sta[maxn],top;
struct Tree
{
struct Edge{int to,v,id,next;}edge[maxm]; int first[maxn],le;
void in(int x,int y,int v,int id) {Edge &e=edge[le];e.to=y;e.v=v;e.id=id;e.next=first[x];first[x]=le++;}
void insert(int x,int y,int v,int id) {in(x,y,v,id); in(y,x,v,id);}
bool vis[maxn],ok; int select,selectv;
void clear()
{
memset(vis,,sizeof(vis)); ok=;
memset(first,,sizeof(first)); le=;
}
void dfs(int x,int fa,int Min,int Minid)
{
if (ok) return;
if (x==bel[t])
{
ok=;
if (selectv+Min<ans)
{
ans=selectv+Min;
numofans=;
whoisans[]=select; whoisans[]=Minid;
}
return;
}
vis[x]=;
for (int i=first[x];i && !ok;i=edge[i].next)
{
const Edge &e=edge[i]; if (vis[e.to]) continue;
dfs(e.to,x,min(Min,e.v),e.v<Min?e.id:Minid);
}
}
}T; void tarjan(int x,int f,int who)
{
low[x]=dfn[x]=++Time; sta[++top]=x; vis[x]=;
for (int i=first[x];i;i=edge[i].next)
{
if (i==f || i==(f^) || i==(who<<) || i==((who<<)^)) continue;
const Edge &e=edge[i];
if (!dfn[e.to]) tarjan(e.to,i,who),low[x]=min(low[x],low[e.to]);
else if (vis[e.to]) low[x]=min(low[x],dfn[e.to]);
}
if (low[x]==dfn[x])
{
tot++;
while (sta[top]!=x) bel[sta[top]]=tot,vis[sta[top--]]=;
bel[sta[top--]]=tot,vis[x]=;
}
} void tarjan(int select)
{
top=tot=Time=;
memset(dfn,,sizeof(dfn));
memset(vis,,sizeof(vis));
for (int i=;i<=n;i++) if (!dfn[i]) tarjan(i,,select);
if (bel[s]==bel[t]) return;
T.clear();
for (int i=;i<=n;i++)
for (int j=first[i];j;j=edge[j].next) if ((j>>)!=select)
{
const Edge &e=edge[j];
if (bel[i]!=bel[e.to]) T.in(bel[i],bel[e.to],e.v,j>>);
}
T.select=select; T.selectv=edge[select<<].v;
T.dfs(bel[s],,0x7fffffff,);
if (!T.ok) {if (edge[select<<].v<ans) {ans=edge[select<<].v; numofans=; whoisans[]=select;}}
} int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
for (int i=,x,y,v;i<=m;i++) scanf("%d%d%d",&x,&y,&v),insert(x,y,v);
dfs(s);
if (ll==) {puts("0\n0"); return ;}
numofans=-; ans=0x7fffffff;
for (int i=;i<=ll;i++) tarjan(list[i]);
if (numofans==-) puts("-1");
else
{
printf("%d\n%d\n",ans,numofans);
for (int i=;i<=numofans;i++) printf("%d ",whoisans[i]);
}
return ;
}
最新文章
- 网页特效:用CSS3制作3D图片立方体旋转特效
- My first blog in cnblog
- Mybatis中SqlMapper配置的扩展与应用(3)
- c++ learning note
- 捕获EF提交异常
- STL--集和多集(set/multiset)
- Android开发视频学习(1)
- 用JS的for循环打印九九乘法表
- java二维码之利用谷歌的zxing生成二维码,解析二维码
- mysq常用l性能分析方法
- 【Mysql】复制表结构+数据(转)
- dojo里添加目录树
- 【题解】 bzoj4472: [Jsoi2015]salesman (动态规划)
- LintCode: 3 Sum
- ASP.NET下跨应用共享Session和使用Redis进行Session托管
- CSS选择器学习小结
- rabbitmq之后台管理和用户设置(三)
- Cocos2d-x 3.0 Lua编程 之 响应Android手机的按键
- centos 虚拟机中修改屏幕分辨率
- YourUninstaller注册码(可用)