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 ;
}

最新文章

  1. 网页特效:用CSS3制作3D图片立方体旋转特效
  2. My first blog in cnblog
  3. Mybatis中SqlMapper配置的扩展与应用(3)
  4. c++ learning note
  5. 捕获EF提交异常
  6. STL--集和多集(set/multiset)
  7. Android开发视频学习(1)
  8. 用JS的for循环打印九九乘法表
  9. java二维码之利用谷歌的zxing生成二维码,解析二维码
  10. mysq常用l性能分析方法
  11. 【Mysql】复制表结构+数据(转)
  12. dojo里添加目录树
  13. 【题解】 bzoj4472: [Jsoi2015]salesman (动态规划)
  14. LintCode: 3 Sum
  15. ASP.NET下跨应用共享Session和使用Redis进行Session托管
  16. CSS选择器学习小结
  17. rabbitmq之后台管理和用户设置(三)
  18. Cocos2d-x 3.0 Lua编程 之 响应Android手机的按键
  19. centos 虚拟机中修改屏幕分辨率
  20. YourUninstaller注册码(可用)

热门文章

  1. 435 Non-overlapping Intervals 无重叠区间
  2. 客户端负载均衡 - Ribbon
  3. SpringBoot_整合视图层技术
  4. HashMap和List遍历方法总结及如何遍历删除元素
  5. vim插件minibuf配置
  6. Django model 反向引用中的related_name
  7. Jenkins .NET项目持续集成配置
  8. 基于C++11的call wrapper
  9. Farseer.net轻量级ORM开源框架 V1.x 入门篇:存储过程数据操作
  10. js 作用域 ?????