UVA 12017 Imitation 【有向图传递闭包的几个结论】【2011上海邀请赛I题】

题目大意是给你一个1000个点10000条边的有向图,让你求出与原图等价的传递闭包的最少边和最多边。
解法:
最多边好求,就dfs一下(floyd的邻接表版)算出闭包,统计一下邻接矩阵中1的个数再减去自环即为答案。
最少边稍微复杂一点:
首先图的强联通分量内的边都是必要边,而两两分量之间去掉多重边即可。
关键点是多重边的去除:强联通分量缩点以后,在新图上从每点开始用bfs或者dp做最长路(因为如果某条重复边跨越了某条路径的话,那么对于路径起点来说,路径终点的距离一定不是由这条重复边松弛的),对于每个点,存在几个距离为1的点计数器就加几,然后再加上每个强联通分量之中的边数即可(对于点数大于1的强联通分量,边数=点数)。
纠结,知道怎么捉,不知怎么说,我太弱了。对于纯图论的问题的想法还是太弱了。

附代码:
#include <iostream>
#include 
<cstdio>
#include 
<cstring>
using namespace std;
#include 
<queue>
#define maxn 1005
#define maxm 10005
bool map[maxn][maxn];
int n,m,tot,newtot;
int st[maxn];
int sc[maxn],newst[maxn],pre[maxn],low[maxn],s[maxn],color[maxn];
bool vis[maxn];
bool viscolor[maxn],colorvis[maxn];
int N,cnt0,cnt1;
int d[maxn];
int mmm,MMM;
struct edge
{
    
int p,next;
    edge(){}
    edge(
int a,int b):p(a),next(b){}
}e[maxm],newe[maxm];
void init()
{
    newtot 
= 0;
    tot 
= cnt0 = cnt1 = N = 0;
    fill(newst,newst 
+ n + 1,-1);
    fill(st,st 
+ n + 1,-1);
    fill(vis,vis 
+ n + 1,0);
    fill(color,color 
+ n + 1,0);
    fill(pre,pre 
+ n + 1,-1);
    fill(low,low 
+ n + 1,-1);
    
for(int i = 1;i <= n;i++)
        
for(int j = 1;j <= n;j++)
        {
            
if(i == j)
                map[i][j] 
= 1;
            
else
                map[i][j] 
= 0;
        }
}
void add(int p,int q)
{
    e[tot] 
= edge(q,st[p]);
    st[p] 
= tot++;
}
void newadd(int p,int q)
{
    newe[newtot] 
= edge(q,newst[p]);
    newst[p] 
= newtot++;
}
void dfs(int u,int v)
{
    map[u][v] 
= 1;
    
for(int k = st[v];~k;k = e[k].next)
        
if(map[u][e[k].p] == 0)
            dfs(u,e[k].p);
}
void scc(int now)
{
    
int v,mm;
    mm 
= low[now] = pre[now] = cnt0++;
    s[N
++= now;
    
for(int k = st[now];~k;k = e[k].next)
    {
        
if(pre[e[k].p] == -1)
            scc(e[k].p);
        
if(low[e[k].p] < mm)
            mm 
= low[e[k].p];
    }
    
if(mm < low[now])
    {
        low[now] 
= mm;
        
return ;
    }
    
do
    {
        sc[(v 
= s[--N])] = cnt1;
        low[v] 
= n;
    }
while(s[N] != now);
    cnt1
++;
}
void bfs(int x)
{
    fill(d,d 
+ cnt1 + 1,0);
    queue 
<int> Q;
    Q.push(x);
    
while(!Q.empty())
    {
        
int now = Q.front();
        Q.pop();
        
for(int k = newst[now];~k;k = newe[k].next)
        {
            
if(d[newe[k].p] < d[now] + 1)
            {
                d[newe[k].p] 
= d[now] + 1;
                Q.push(newe[k].p);
            }
        }
    }
    
for(int i = 0;i < cnt1;i++)
        
if(d[i] == 1)
            mmm
++;
}
void gao()
{
    scanf(
"%d %d",&n,&m);
    init();
    
for(int i = 0;i < m;i++)
    {
        
int a,b;
        scanf(
"%d %d",&a,&b);
        add(a,b);
    }
    
for(int i = 1;i <= n;i++)
        dfs(i,i);
    mmm 
= 0,MMM = 0;
    
for(int i = 1;i <= n;i++)
        
for(int j = 1;j <= n;j++)
            
if(map[i][j])
                MMM
++;
    MMM 
-= n;
    
for(int i = 1;i <= n;i++)
        
if(pre[i] == -1)
            scc(i);
    
for(int i = 1;i <= n;i++)
    {
        color[sc[i]]
++;
        
for(int k = st[i];~k;k = e[k].next)
            
if(sc[i] != sc[e[k].p])
                newadd(sc[i],sc[e[k].p]);
    }
    
for(int i = 0;i < cnt1;i++)
        bfs(i);
    
for(int i = 0;i < n;i++)
        
if(color[i] > 1)
            mmm 
+= color[i];
    printf(
"%d %d\n",mmm,MMM);
}
int main()
{
    
int t;
    scanf(
"%d",&t);
    
for(int i = 1;i <= t;i++)
    {
        printf(
"Case #%d: ",i);
        gao();
    }
}

posted on 2011-09-08 20:10 BUPT-[aswmtjdsj] @ Penalty 阅读(523) 评论(0)  编辑 收藏 引用 所属分类: 图论UVAlive Solution Report


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年9月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

导航

统计

常用链接

留言簿(1)

随笔分类(150)

随笔档案(71)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜