添边问题

( 程序文件名： stock. pas/c/cpp) 【问题描述】 没有环的有向图称为有向无环图，这是一个多么美好的结构吖。 如果有一张有 N 个点的有向图，我们可能需要删掉一些边使它变成一张有向 无环图。 假设初始时我们只有 N 个互不相连的点，当然它也是一张有向无环图。依次 给出 T 条边和每条边的方向。每给出一条边就要立即决定是否要加入这一条 边，使得这张图始终是一张有向无环图。计算在满足要求的情况下一共有多 少条边没有被加入。如果所有边都可以加入这张图则输出 0。 【输入文件】文件名： stock.in 第一行为两个整数：N(1<=N<=250)，T(0<=T<=500,000)。接下来 T 行，每 行两个整数 x,y(1 <= x , y <= N)，表示一条从 x 到 y 的单向边。 【输出文件】文件名： stock.out 一个整数，表示没有被加入的边数。 【样例输入】 3 6 1 2 1 3 3 1 2 1 1 2 2 3 【样例输出】 2 【样例说明】 1-->2，之前 2-->1 没有路径，不会造成环，加入 1-->3，之前 3-->1 没有路径，不会造成环，加入 3-->1，之前 1-->3 有路径，使得图有环，不加入 2-->1，之前 1-->2 有路径，不加入 1-->2 , 之前 2-->1 没有路径，加入 2-->3，之前 3-->2 没有路径，加入

因此答案是 2

分析： 

 题目大意：图论的基础题。依次读入T条边，如果添入这条边会出现环则不加入。问没有被加入的边的数量。

     我们想一想如果这条边(x→y)加入之后不会造成环的话，则加入这条边。如果加入这条边之后使得图有环的话，那么这条边肯定是环的一部分，那么y到x也肯定有一条路径使y与x连通。  我们用一个数组mat[x][y]表示x到y是否有路径连通。  于是判定一条边是否能加入的条件如下：  

x==y时，不加入  mat[y][x]==1时，不加入 。 否则一定加入。  

方法一：每加入一条边之后用floyed判断两点之间是否连通。O(n^3) 分值：60； 代码;

program ex02; var i,j,n,m,k,x,y,ans:longint; f:array[1..250,1..250] of boolean; begin assign(input,'stock.in'); assign(output,'stock.out'); reset(input); rewrite(output); fillchar(f,sizeof(f),false); ans:=0; readln(n,m); for i:=1 to n do f[i,i]:=true; for i:=1 to m do begin readln(x,y); if (f[y,x])or(x=y) then inc(ans) else begin f[x,y]:=true;//核心代码 for j:=1 to n do for k:=1 to n do //if (j<>k)and(j<>x)and(j<>y)and(k<>x)and(k<>y)and(x<>Y) then if f[j,x] and f[y,k] then f[j,k]:=true; end; end; write(ans); close(input); close(output); end. 其实还有一个搜索版本的:由于减少了一些不必要的计算理想得分:70;

#include<iostream> #include<cstdio> #include<cstring> #include<iostream> using namespace std; int g[300][300]; int chu[300]; int n,t,cnt=0; int vis[300]; int dfs(int x) { vis[x]=-1; for(int i=1;i<=chu[x];i++) { if(vis[g[x][i]]<0) return 0; else if(!vis[g[x][i]]&&!dfs(g[x][i])) return 0; } vis[x]=1; return 1; } int main() { freopen("stock.in","r",stdin); freopen("stock.out","w",stdout); scanf("%d%d",&n,&t); int x,y; for(int i=1;i<=t;i++) { scanf("%d%d",&x,&y); g[x][++chu[x]]=y; memset(vis,0,sizeof(vis)); int t=1; vis[x]=-1;//搜索y到x是否连通. t=dfs(y); if(t==0) {cnt++;chu[x]--;} } printf("%d\n",cnt); } 方法二： 

       加入的时候首先判断mat[x][y]==1是否成立，不成立的话则需进行更新。因此目前的关键问题就是如何高效的进行mat矩阵的更新操作。   

       对于每次加入的边(x,y)，影响到的点无非两类：

原来能到x但到不了y的；原来从x不能到但从y能到的。        我们分别设这两个列表为a[la]和b[lb]，并令a[++la]=x,b[++lb]=y。两个点集间的mat值一定是从0变到1，每次二重循环进行更新。因为每次几乎没有多少冗余更新，因此均摊的复杂度相当低，可以完美的解决此题。  

      题目没什么难点，要说trick也就是重边和自环，但是显然这种边违背题意，是不能加的。

代码：

#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=256; int read() { int x=0,f=1; char ch; ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f; } int n,m,cnt; int a[N],b[N]; bool mat[N][N]; int main() { freopen("stock.in","r",stdin); freopen("stock.out","w",stdout); n=read(); m=read(); int x,y,i,j,k,la,lb; for(i=1;i<=m;i++) { x=read(); y=read(); if(x==y||mat[y][x]) cnt++; else { la=lb=1;a[1]=x;b[1]=y; for(j=1;j<=n;j++) if(mat[j][x]&&!mat[j][y]) a[++la]=j; for(j=1;j<=n;j++) if(mat[y][j]&&!mat[x][j]) b[++lb]=j; for(j=1;j<=la;j++) for(k=1;k<=lb;k++) mat[a[j]][b[k]]=1; } } printf("%d\n",cnt); fclose(stdin); fclose(stdout); return 0; }