USACO 2007 March Contest, Silver Problem 1. Cow Traffic

PROBLEM

The bovine population boom down on the farm has caused serious congestion on the cow trails leading to the barn. Farmer John has decided to conduct a study to find the bottlenecks in order to relieve the 'traffic jams' at milking time.

The pasture contains a network of M (1 ≤ M ≤ 50,000) one-way trails, each of which connects exactly two different intersections from the set of N (1 ≤ N ≤ 5,000) intersections conveniently numbered 1..N; the barn is at intersection number N. Each trail connects one intersection point to another intersection point with a higher number. As a result, there are no cycles and, as they say on the farm, all trails lead to the barn. A pair of intersection points might be connected by more than one trail.

During milking time rush hour, the cows start from their respective grazing locations and head to the barn. The grazing locations are exactly those intersection points with no trails connecting into them. Each cow traverses a 'path', which is defined as a sequence of trails from a grazing location to the barn.

Help FJ finding the busiest trail(s) by computing the largest number of possible paths that contain any one trail. The answer is guaranteed to fit in a signed 32-bit integer.

INPUT FORMAT:

Line 1: Two space-separated integers: N and M.

Lines 2..M+1: Two space-separated intersection points.

OUTPUT FORMAT:

Line 1: The maximum number of paths passing through any one trail.

SAMPLE INPUT

7 7
1 3
3 4
3 5
4 6
2 3
5 6
6 7

SAMPLE OUTPUT

4 

 

USACO ANALYSIS

USACO MAR07 Problem 'traffic' Analysis

by Kaan Soral, Onur Soral and Cihat Imamoglu from Turkey

Problem: The problem is straightforward: what is edge on which maximum number of paths pass? It can be any edge of the graph, the problem is to find the number of the maximum paths. Note that the edge might appear closer to the cow's pastures than the barn; the path might be in the middle of the 'graph'.

A path always starts from a source node which has an in-degree of zero and it ends at the sink, which is always N.

Solution: The main idea is that, for an edge: The number of paths that passes through is equal to (I)*(II) where:

• (I): the number of ways from the ending node of an edge to the sink node (N) (we will find this from the original graph)
• (II): the number of ways from the starting node of an edge to the source nodes (we will find this from the transposed graph)

We will compute this for all edges and the solution will be the maximum of all.

To find (I) we will use dynamic programming, since the graph comes topologically sorted and there are no cycles, our job is fairly easy.

Initial state is forward[N]=1; (the number of ways that leads us to Nth node from Nth node is 1)

for(i=N-1; i>=1; i--) {
            // the number of ways that lead us from vertex i to vertex N is the sum of all
                // forward values of nodes to which i has a forward edge for all nd's
        forward[i] = forward[i] + forward[nd] // so we have computed 'nd' before
                                                      // ('nd' is a node to which i has an edge)
            // nd >= i (topologically sorted)
            //forward[i] is the sum of all forward[nd]'s  
}

 

To find (II) we will construct a transposed graph, (all edges such x->y will become y->x, i.e., their directions will be reversed.) For all nodes i that don't have an incoming edge (for transposed graph don't have an outgoing edge), backward[i]=1 ( to determine the source nodes )

for (i=1; i<=N; i++) {  
        // we compute bacward values the same way, we did as forwards }
        // backward[i] is the number of paths from i'th node to source nodes in transposed graph 
        // now it should be very logical that the number
        // of paths from sources to the sink for i'th node is
        // backward[i]*forward[i] and for an edge, it is,
        // forward[end node]*backward[start node], we can
        // think an edge as a node, nothing changes
}

 

Complexity: The computation of backward and forward array is both O(N+M),and the for loop is O(N). In the total, the edge number assigns the complexity as O(N+M) All computations are O(N+M) since we use adjacency list, it would be O(N^2) for adjacency matrix.

Here is the code:

#include <stdio.h>
#include <stdlib.h>
#define MAXN 5100
#define MAXM 51000  

typedef struct node {
    int num;
    struct node *next;
} node;

node *newNode(int num) {
    node *temp=(node *)malloc(sizeof(node));
    temp->num=num; temp->next=NULL;
    return temp;
}

node *arrf[MAXN],*arrb[MAXN],*endf[MAXN],*endb[MAXN];        /* Adjacency matrix is used because
                                                  matrix is sparse and there can
                                                                be MORE THAN ONE from one edge */
int N, M, MAX;
int forward[MAXN], backward[MAXN];
int inf[MAXN], endp[MAXM], stp[MAXM];                        /* 'inf' counts the number of edges that goes in a node */
                                                             /* 'stp' is the start point and 'endp' is the end point of an edge */

void read(void) {
    FILE *input=fopen("traffic.in","r");
    fscanf(input," %d %d",&N,&M);
    int i,x,y;
    for(i=1;i<=M;i++) {
        fscanf(input," %d %d",&x,&y);
        inf[y]++;
        stp[i]=x; endp[i]=y;
        if(arrf[x]==NULL) {
            arrf[x]=newNode(y);
            endf[x]=arrf[x];
        } else {                                              /* 'arrf' and 'endf' is for normal graph, adjacency list */
            endf[x]->next=newNode(y);
            endf[x]=endf[x]->next;
        }
        if(arrb[y]==NULL) {
            arrb[y]=newNode(I);
            endb[y]=arrb[y];
        } else {                                              /* 'arrb' and 'endb' is for traversed graph, adjacency list */
            endb[y]->next=newNode(I);
            endb[y]=endb[y]->next;
        }
    }
}

void find(void) {
    int i;
    node *current;
    forward[N]=1;                                            /* Initial state of 'forward' which is for the number of ways i to N */
    for(i=N-1;i>=1;i--) {                                    /* The graph is topologically sorted */
        current=arrf[i];
        while(current!=NULL) {
            forward[i]+=forward[current->num];               /* forward[i] is the sum of forwards of nodes that i has edge to, current->num <= i */
            current=current->next;
        }
    }
    for(i=1; i<=N; i++)
        if(!inf[i])
            backward[i]=1;                                   /* Initial state of 'backward' which is for the number of ways i to sink nodes*/
                                                             /* backward[i] is 1 for all nodes which have no inner edge, start nodes of paths, sink nodes */    
    for(i=1;i<=N;i++) {                                      /* For starts from 1 to N because in traversed graph current->num is always> =i  */
        current=arrb[i];
        while(current!=NULL) {
            backward[i]+=backward[current->num];
            current=current->next;
        }
    }
    for(i=1;i<=M;i++) {
        if(forward[endp[i]]*backward[stp[i]]>MAX)
             MAX=forward[endp[i]]*backward[stp[i]];          /* For all edges, the number of paths that goes through it is multiplication of */
    }                                                        /* (sum of ways from its start point to source nodes (backward[stp[i]]) )
                                                                X (sum of ways from its end point to sink node,N (forward[endp[i]]) )   */
}

void write(void) {
    FILE *output=fopen("traffic.out","w");
    fprintf(output,"%d\n",MAX);
    fclose(output);
}

int main() {
    read();
    find();
    write();
    return 0;
}

 

程序

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5000 + 1;
const int MAX_M = 50000 + 1;
int n, m, EdgeCount = 0, In[MAX_N], Out[MAX_N], F[MAX_N], ReverseF[MAX_N];
vector<int> Head[MAX_N], ReverseHead[MAX_N];
int main()
{
    cin >> n >> m;
    int x,y;
    for (int i = 1; i <= m; i++)
    {
        cin >> x >> y;
        Head[min(x,y)].push_back(max(x,y));
        ReverseHead[max(x,y)].push_back(min(x,y));
        In[max(x,y)]++;
        Out[min(x,y)]++;
    }
    queue<int> Q;
    for(int i=1;i<=n;i++)
        if(!In[i])
        {
            F[i]=1;
            Q.push(i);
        }
    while(!Q.empty())
    {
        int Top = Q.front();
        Q.pop();
        for(int j=0; j<Head[Top].size(); j++)
        {
            F[Head[Top][j]] += F[Top];
            In[Head[Top][j]]--;
            if(!In[Head[Top][j]])
                Q.push(Head[Top][j]);
        }
    }
    ReverseF[n]=1;
    Q.push(n);
    while(!Q.empty())
    {
        int Top=Q.front();
        Q.pop();
        for(int j=0; j<ReverseHead[Top].size(); j++)
        {
            ReverseF[ReverseHead[Top][j]] += ReverseF[Top];
            Out[ReverseHead[Top][j]]--;
            if(!Out[ReverseHead[Top][j]])
                Q.push(ReverseHead[Top][j]);
        }
    }
    int ans;
    for(int i=1; i<=n; i++)
        for(int j=0; j<Head[i].size(); j++)
            ans = max(ans,F[i]*ReverseF[Head[i][j]]);
    cout << ans << endl;
    return 0;
}

 

分析

不难想到：一条边的经过次数是从入度为0的点到这条边的起点的路径数与从这条边的终点到点n的路径数的积。（简单的乘法原理）

然后想到，先正向动规，然后进行反向动规。

下面是正向动规的代码，反向动规是差不多的：

while(!Q.empty())
{
    int Top = Q.front();
    Q.pop();
    for(int j=0; j<Head[Top].size(); j++)
    {
        F[Head[Top][j]] += F[Top];
        In[Head[Top][j]]--;
        if(!In[Head[Top][j]])
            Q.push(Head[Top][j]);
    }
}

首先建立一个队列Q，队列中存储入度非零的点。然后把队列扫一遍，弹出队头的点。第5~11行，找所有以这个点为起点的边（Head[Top]），累加从放牧点到这条边的终点的路径数。递减这条边的终点的入度，直到为零。压入这个终点作为要分析的点。

反向动规的概念差不多，只不过在不同的数组中进行操作罢了。

最后简单的一个擂台法找最大值。

思路不难，但是当中正反图的操作逻辑有点搞脑子，一定要把思路理顺，搞清楚这几个数组的关系到底是什么，比如F[]是路径数，而Head[]中存储的是边的终点。那么F[Head[][]]的形式指的是什么也就不难理解了。还有要彻底相同弹出和压入队列的思路是什么。

（比如我一开始没有搞清楚读入是对于In和Out数组累加的关系，结果In和Out两个数组写反了）