P2883 [USACO07MAR]牛交通Cow Traffic

随着牛的数量增加，农场的道路的拥挤现象十分严重，特别是在每天晚上的挤奶时间。为了解决这个问题，FJ决定研究这个问题，以能找到导致拥堵现象的瓶颈所在。

牧场共有M条单向道路，每条道路连接着两个不同的交叉路口，为了方便研究，FJ将这些交叉路口编号为1..N,而牛圈位于交叉路口N。任意一条单向道路的方向一定是是从编号低的路口到编号高的路口，因此农场中不会有环型路径。同时，可能存在某两个交叉路口不止一条单向道路径连接的情况。

在挤奶时间到来的时候，奶牛们开始从各自的放牧地点回到牛圈。放牧地点是指那些没有道路连接进来的路口（入度为0的顶点）。

现在请你帮助fj通过计算从放牧点到达牛圈的路径数目来找到最繁忙的道路（答案保证是不超过32位整数）。

思维固化了。

看到这题直接套上P1685 游览的板子。

才得60分。

再读题（看题解），发现这题会有多个起点，多个终点。

那么对于多个终点，只能去n，所以还要从n建反边跑一边拓扑排序，这样一条边的贡献就是\(g(u)*f(v)\)。

好像我用了最笨的方法跑两边拓扑排序。

code：

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int wx=500017;inline int read(){    int sum=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}    while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}    return sum*f;}int n,m,ans;int num,tot;int g[wx],head[wx],h[wx],f[wx];int in[wx],out[wx],in2[wx],out2[wx];struct e{    int nxt,to;}edge[wx*2];void add(int from,int to){    edge[++num].nxt=head[from];    edge[num].to=to;    head[from]=num;}struct ee{    int nxt,to;}e[wx*2];void ADD(int from,int to){    e[++tot].nxt=h[from];    e[tot].to=to;    h[from]=tot;}queue
       
         q;void bfs1(){    for(int i=1;i<=n;i++)if(!in[i])g[i]=1,q.push(i);    while(q.size()){        int u=q.front(); q.pop();        for(int i=head[u];i;i=edge[i].nxt){            int v=edge[i].to;            g[v]+=g[u];            in[v]--;            if(!in[v]){                q.push(v);            }        }    }}void bfs2(){    for(int i=1;i<=n;i++)if(!in2[i])f[i]=1,q.push(i);    while(q.size()){        int u=q.front(); q.pop();        for(int i=h[u];i;i=e[i].nxt){            int v=e[i].to;            f[v]+=f[u];            in2[v]--;            if(!in2[v])q.push(v);        }    }    for(int u=1;u<=n;u++){        for(int i=head[u];i;i=edge[i].nxt){            int v=edge[i].to;            ans=max(ans,g[u]*f[v]);        }    }}int main(){    n=read(); m=read();    for(int i=1;i<=m;i++){        int x,y;         x=read(); y=read();        if(x>y)swap(x,y);        add(x,y); in[y]++; out[x]++;        ADD(y,x); in2[x]++; out2[y]++;    }    bfs1();    bfs2();    printf("%d\n",ans);    return 0;}