洛谷 P2936 [USACO09JAN]全流Total Flow

題目描述

Farmer John always wants his cows to have enough water and thus has made a map of the N (1 <= N <= 700) water pipes on the farm that connect the well to the barn. He was surprised to find a wild mess of different size pipes connected in an apparently haphazard way. He wants to calculate the flow through the pipes.

Two pipes connected in a row allow water flow that is the minimum of the values of the two pipe's flow values. The example of a pipe with flow capacity 5 connecting to a pipe of flow capacity 3 can be reduced logically to a single pipe of flow capacity 3:

+---5---+---3---+    ->    +---3---+

Similarly, pipes in parallel let through water that is the sum of their flow capacities:

+---5---+

---+       +---    ->    +---8---+

+---3---+

Finally, a pipe that connects to nothing else can be removed; it contributes no flow to the final overall capacity:

---+               ->    +---3---+

+---3---+--

All the pipes in the many mazes of plumbing can be reduced using these ideas into a single total flow capacity.

Given a map of the pipes, determine the flow capacity between the well (A) and the barn (Z).

Consider this example where node names are labeled with letters:

+-----------6-----------+

A+---3---+B                      +Z

+---3---+---5---+---4---+

C       D

Pipe BC and CD can be combined:

+-----3-----+-----4-----+

D Then BD and DZ can be combined:

+-----------3-----------+

Then two legs of BZ can be combined:

B A+---3---+---9---+Z

Then AB and BZ can be combined to yield a net capacity of 3:

A+---3---+Z

Write a program to read in a set of pipes described as two endpoints and then calculate the net flow capacity from 'A' to 'Z'. All

networks in the test data can be reduced using the rules here.

Pipe i connects two different nodes a_i and b_i (a_i in range

'A-Za-z'; b_i in range 'A-Za-z') and has flow F_i (1 <= F_i <= 1,000). Note that lower- and upper-case node names are intended to be treated as different.

The system will provide extra test case feedback for your first 50 submissions.

約翰總希望他的奶牛有足夠的水喝，是以他找來了農場的水管地圖，想算算牛棚得到的水的 總流量.農場裡一共有N根水管.約翰發現水管網絡混亂不堪，他試圖對其進行簡 化.他簡化的方式是這樣的：

兩根水管串聯，則可以用較小流量的那根水管代替總流量.

兩根水管并聯，則可以用流量為兩根水管流量和的一根水管代替它們

當然，如果存在一根水管一端什麼也沒有連接配接，可以将它移除.

請寫個程式算出從水井A到牛棚Z的總流量.資料保證所有輸入的水管網絡都可以用上述方法 簡化.

輸入輸出格式

輸入格式：

• Line 1: A single integer: N
• Lines 2..N + 1: Line i+1 describes pipe i with two letters and an integer, all space-separated: a_i, b_i, and F_i

輸出格式：

• Line 1: A single integer that the maximum flow from the well ('A') to the barn ('Z')

輸入輸出樣例

輸入樣例#1：

5 
A B 3 
B C 3 
C D 5 
D Z 4 
B Z 6 
      

輸出樣例#1：

3 
      

吐槽//或者這次該叫反思感想什麼的吧

　　不知怎麼了，可能是連續一周每天4.5h的睡眠造成的吧。難題根本不想看不想寫，就寫道裸題放松一下吧。國賽将近，亞曆山大啊……

解題思路

　　最大流裸題，套闆子吧。不過這題字元輸入方法值得學習。

源代碼

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
int n,m;
struct Edge{
    int next,to,flow;
}e[10010]={0};
int cnt=2,head[500]={0};
void add(int u,int v,int f)
{
    e[cnt]={head[u],v,f};
    head[u]=cnt++;
    e[cnt]={head[v],u,0};
    head[v]=cnt++;
}
int s=1,t=26;
int dis[500]={0};
bool bfs()
{
    std::queue<int> q;
    memset(dis,0,sizeof(dis));
    q.push(s);
    dis[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[v]||!e[i].flow) continue;
            dis[v]=dis[u]+1;
            q.push(v);
        }
    }
    return dis[t]!=0;
}

int dfs(int u,int f)
{
    if(f==0||u==t) return f;
    int flow_sum=0;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(dis[v]!=dis[u]+1||!e[i].flow) continue;
        int temp=dfs(v,std::min(e[i].flow,f-flow_sum));
        e[i].flow-=temp;
        e[i^1].flow+=temp;
        flow_sum+=temp;
        if(flow_sum>=f) break;
    }
    if(flow_sum==0) dis[u]=-1;
    return flow_sum;
}

int dinic()
{
    int ans=0;
    while(bfs())
    {
        while(int temp=dfs(s,0x7fffffff)) ans+=temp;
    }
    return ans;
}

int main()
{
    scanf("%d",&n);
    for(int i=1,f;i<=n;i++)
    {
        char u[2],v[2];
        scanf("%s%s%d",u,v,&f);
        add(u[0]-'A'+1,v[0]-'A'+1,f);
    }
    printf("%d\n",dinic());
    return 0;
}