破坏行动问题

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1866

破坏行动问题

Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^

题目描述

恐怖组织伊阿德尔卡的首领拉本·灯打算摧毁一个敌对势力的石油运输系统。这个石油运输系统可以看成一个运输网络，由许多的结点和连接结点的管道构成。只有地点A生产石油，而生产的石油则通过管道输送到地点B，石油不能在中间结点累积。管道是双向的，每条管道连接两个不同的结点，而每两个结点间最多只有一条管道相连。每条管道有一个抗压指数，当石油的流量超过这个数管道就会爆炸。A地生产石油的速度可以认为是非常快的，但由于管道抗压指数的原因，能运到B的有一个上限。拉本·灯知道敌对势力采用了某种方案使得他们能输送最多的石油，但他不知道这个具体的方案是什么。拉本·灯有一种特殊的物质，可以让一条管道的抗压指数下降1。作为伊阿德尔卡首席恐怖程序员，你的任务就是告诉拉本·灯，让哪些管道的抗压指数下降，一定可以使管道爆炸从而摧毁运输网络。

输入

第1行包含四个整数n，m，s，t，表示有n个结点（编号为1，2，3，…，n），m条管道，s，t分别是A地和B地的编号。2<=n<=130，0<=m<=n(n-1)/2，1<=s，t<=n。
接下来m行每行描述一条管道，包含3个整数i，j，c。i和j分别为管道连接的2个结点，c为这条管道的抗压指数。1<=i,j<=n，1<=c<=10000。

输出

第1行输出抗压指数减少1就必定爆炸的管道条数k。
接下来k行每行输出一个整数p（1<=p<=m），说明第p条管道如果抗压指数减少1就必定爆炸。序号p按照管道输入的顺序，并按照p的升序输出。

示例输入

示例输出

2
2
4

分析：首先跑一遍网络流，然后在残留网络中判断任意两点的连通性，加入联通则有流量盈余，自然用floyd判断连通性即可，复杂度是n三方，然后遍历所有的边，O(m)。

#include"stdio.h"
#include"string.h"
#include"queue"
#include"stack"
#include"algorithm"
#include"vector"
#include"iostream"
#include"math.h"
#include"map"
#include"stdlib.h"
#define M 222
#define inf 100000000
using namespace std;
struct node
{
    int u,v,w,next;
}edge[M*M];
int t,head[M],dis[M],dist[M][M],vis[M];
void init()
{
    t=0;
    memset(head,-1,sizeof(head));
}
void add(int u,int v,int w)
{
    edge[t].u=u;
    edge[t].v=v;
    edge[t].w=w;
    edge[t].next=head[u];
    head[u]=t++;
    edge[t].u=v;
    edge[t].v=u;
    edge[t].w=w;
    edge[t].next=head[v];
    head[v]=t++;
}
int bfs(int S,int T)
{
    queue<int>q;
    memset(dis,-1,sizeof(dis));
    dis[S]=0;
    q.push(S);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v;
            if(edge[i].w&&dis[v]==-1)
            {
                dis[v]=dis[u]+1;
                if(v==T)
                    return 1;
                q.push(v);
            }
        }
    }
    return 0;
}
int dfs(int cur,int a,int T)
{
    if(cur==T)return a;
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(edge[i].w&&dis[v]==dis[cur]+1)
        {
            int tt=dfs(v,min(edge[i].w,a),T);
            if(tt)
            {
                edge[i].w-=tt;
                edge[i^1].w+=tt;
                return tt;
            }
        }
    }
    return 0;
}
void Dinic(int S,int T)
{
    int ans=0;
    while(bfs(S,T))
    {
        while(int tt=dfs(S,inf,T))
            ans+=tt;
    }
}
void floyd(int n)
{
    int i,j,k;
    for(k=1;k<=n;k++)
    {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(dist[i][j]>dist[i][k]+dist[k][j])
                    dist[i][j]=dist[i][k]+dist[k][j];
            }
        }
    }
}
int main()
{
    int i,j,n,m,st,sd,a,b,c;
    while(scanf("%d%d%d%d",&n,&m,&st,&sd)!=-1)
    {
        init();
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
        }
        Dinic(st,sd);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(i==j)dist[i][j]=0;
                else dist[i][j]=inf;
            }
        }
        for(i=0;i<t;i++)
        {
            int u=edge[i].u;
            int v=edge[i].v;
            if(edge[i].w)
            dist[u][v]=edge[i].w;
        }
        floyd(n);
        int num=0;
        for(i=0;i<t;i+=2)
        {
            int u=edge[i].u;
            int v=edge[i].v;
            if(dist[u][v]<inf&&dist[v][u]<inf)continue;
            vis[num++]=i/2+1;
        }
        printf("%d
",num);
        for(i=0;i<num;i++)
            printf("%d
",vis[i]);
        return 0;
    }
    return 0;
}