網絡流入門試題 [最大流]運輸問題1 maxflowa

題目連結：http://cogs.yeefanblog.tk/t/11

Title: 运输问题1

Input: maxflowa.in

Output: maxflowa.out

Time Limit: 1000 ms

Memory Limit: 128 MB

Level: ★★☆

【问题描述】

    一个工厂每天生产若干商品，需运输到销售部门进行销售。从产地到销地要经过某些城镇，有不同的路线可以行走，每条两城镇间的公路都有一定的流量限制。请你计算，在不考虑其它车辆使用公路的前提下，如何充分利用所有的公路，使产地运输到销地的商品最多，最多能运输多少商品。

【输入格式】

输入文件有若干行
第一行，一个整数n，表示共有n个城市(2<=n<=100)
下面有n行,每行有n个数字。第p行第q列的数字表示城镇p与城镇q之间有无公路连接。数字为0表示无，大于0表示有公路，且该数字表示该公路流量。

【输出格式】

输出文件有一行
第一行，1个整数n，表示最大流量为n。

【输入输出样例】

输入文件名： maxflowa.in

6
0 4 8 0 0 0
0 0 4 4 1 0
0 0 0 2 2 0
0 0 0 0 0 7
0 0 0 6 0 9
0 0 0 0 0 0

输出文件名：maxflowa.out

8

【分析】

基礎的最大流問題。
由於源點沒有入度、匯點沒有出度，所以由樣例可以看出1號的源點，N號是匯點。
剩下就是用Ford-Fulkerson方法求解最大流即可。
《算法導論》上，Ford-Filkerson方法的偽代碼描述是：
FORD_FULKERSON(G,s,t)
1 for each edge(u,v)∈E[G]
2 do f[u,v] <— 0
3 f[v,u] <— 0
4 while there exists a path p from s to t in the residual network Gf
5 do cf(p) <— min{ cf(u,v) : (u,v) is in p }
6 for each edge(u,v) in p
7 do f[u,v] <— f[u,v]+cf(p)
8 f[v,u] <— -f[u,v]         

【我的代碼】

C++语言: Codee#25004

001 /*
002 *Problem:http://cogs.yeefanblog.tk/t/11
003 *Author:Yee-fan Zhu
004 *Website:http://www.zhuyf.tk/
005 *Method:網絡流 最大流 Full-Fulkerson
006 */
007 #include <iostream>
008 #include <cstdio>
009 #include <cstdlib>
010 #include <cstring>
011 #include <queue>
012 using namespace std;
013
014 const int INF=0x7ffffff;
015 const int MAXN=101;
016 int Map[MAXN][MAXN];
017 int Father[MAXN];
018 bool Used[MAXN];
019 int Ans;
020 int N,M;
021 int S,T;
022
023 void Ford_Fulkerson()
024 {
025     while(1)
026     {
027         queue<int>Q;
028         memset(Used,0,sizeof(Used));
029         memset(Father,0,sizeof(Father));
030
031         int now;
032         Used[S]=true;
033         Q.push(S);
034         while(!Q.empty())
035         {
036             now=Q.front();
037             Q.pop();
038             if(now==T)
039                 break;
040             for (int i=1;i<=N;i++)
041             {
042                 if(Map[now][i] && !Used[i])
043                 {
044                     Father[i]=now;
045                     Used[i]=true;
046                     Q.push(i);
047                 }
048             }
049         }
050
051         if(!Used[T])// There is no Augmenting Path.
052             break;
053
054         int u;
055         int Min=INF;
056         for (u=T;u!=S;u=Father[u])
057         {
058             if(Map[Father[u]][u]<Min)
059                 Min=Map[Father[u]][u];
060         }
061
062         for (u=T;u!=S;u=Father[u])
063         {
064             Map[Father[u]][u]-=Min;
065             Map[u][Father[u]]+=Min;
066         }
067
068         Ans+=Min;
069     }
070 }
071
072 void init()
073 {
074     scanf("%d\n",&N);
075     M=0;
076     memset(Map,0,sizeof(Map));
077
078     int v;
079     for (int i=1;i<=N;i++)
080     {
081         for (int j=1;j<=N;j++)
082         {
083             scanf("%d",&v);
084             Map[i][j]=v;
085             if(v)
086                 M++;
087         }
088     }
089     S=1;
090     T=N;
091     return;
092 }
093
094 int main()
095 {
096     freopen("maxflowa.in","r",stdin);
097     freopen("maxflowa.out","w",stdout);
098     init();
099     Ford_Fulkerson();
100     printf("%d\n",Ans);
101     return 0;
102 }

[並查集]NOI2001 食物鏈 eat 解題報告

Title: 食物链    題目連結：COGS

Input: eat.in

Output: eat.out

Time Limit: 1000 ms

Memory Limit: 128 MB

Level: ★★☆

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：

• 第一种说法是“1 X Y”，表示X和Y是同类。
• 第二种说法是“2 X Y”，表示X吃Y。

此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1. 当前的话与前面的某些真的话冲突，就是假话；
2. 当前的话中X或Y比N大，就是假话；
3. 当前的话表示X吃X，就是假话。

你的任务是根据给定的N（1<=N<=50,000）和K句话（0<=K<=100,000），输出假话的总数。

输入文件
第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。

• 若D=1，则表示X和Y是同类。
• 若D=2，则表示X吃Y。

输出文件
只有一个整数，表示假话的数目。
输入样例
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
输入文件

输出样例

3
样例说明
对7句话的分析

• 1 101 1 假话
• 2 1 2 真话
• 2 2 3 真话
• 2 3 3 假话
• 1 1 3 假话
• 2 3 1 真话
• 1 5 5 真话

「分析」

本題是並查集的經典應用。
每次判斷時，前兩個條件都能O（1）判斷，關鍵在於第3個條件。
由於無法判斷可以另外虛設2*N個物種，分別表示能吃第i個物種的物種和被第i個物種所吃的物種。那麼剩下就是裸並查集了，每次合併就把那個三角環依次合併即可。

「我的代碼」

 

C++语言: Codee#24995

001 /*
002 *Problem: NOI2001-eat
003 *Author: Yee-fan Zhu
004 *Time: Jan 02,2012
005 *Method: UFS
006 */
007 #include <iostream>
008 #include <cstdlib>
009 #include <cstdio>
010 using namespace std;
011 const int MAX=150010;
012
013 int N,K;
014 int Ani[MAX];
015 int Eat[MAX];
016 int Eaten[MAX];
017 int False=0;
018
019 int UFS_Find(int x)
020 {
021     int t,p;
022     p=x;
023     while(Ani[p]!=p)
024         p=Ani[p];
025     while(Ani[x]!=x)  //Compress Path
026     {
027         t=Ani[x];
028         Ani[x]=p;
029         x=t;
030     }
031     return p;
032 }
033
034 bool UFS_Check(int a,int b)
035 {
036     int x=UFS_Find(a);
037     int y=UFS_Find(b);
038     return (x==y);
039 }
040
041 void UFS_Merge(int a,int b)
042 {
043     Ani[UFS_Find(b)]=UFS_Find(a);
044 }
045
046 void init()
047 {
048     scanf("%d %d\n",&N,&K);
049     for (int i=1;i<=N;i++)
050     {
051         int x=N+i;
052         int y=N*2+i;
053         Ani[i]=i,Ani[x]=x,Ani[y]=y;
054         Eaten[i]=x,Eat[i]=y;
055         Eaten[x]=y,Eat[x]=i;
056         Eaten[y]=i,Eat[y]=x;
057     }
058 }
059
060 void work()
061 {
062     int D,X,Y;
063     for (int i=1;i<=K;i++)
064     {
065         scanf("%d %d %d\n",&D,&X,&Y);
066         if(X>N || Y>N)
067         {
068             False++;
069             continue;
070         }
071         if(D==2 && X==Y)
072         {
073             False++;
074             continue;
075         }
076
077         if(D==1)
078         {
079             if(UFS_Check(X,Y))
080                 continue;
081             if(UFS_Check(Eat[X],Y) ||  UFS_Check(Eaten[X],Y) )
082             {
083                 False++;
084                 continue;
085             }
086
087             UFS_Merge(X,Y);
088             UFS_Merge(Eaten[X],Eaten[Y]);
089             UFS_Merge(Eat[X],Eat[Y]);
090             continue;
091         }
092
093         if(D==2)
094         {
095             if(UFS_Check(Eat[X],Y))
096                 continue;
097
098             if(UFS_Check(X,Y) || UFS_Check(Eaten[X],Y))
099             {
100                 False++;
101                 continue;
102             }
103
104             UFS_Merge(Eat[X],Y);
105             UFS_Merge(X,Eaten[Y]);
106             UFS_Merge(Eaten[X],Eat[Y]);
107             continue;
108         }
109     }
110 }
111
112 int main()
113 {
114     freopen("eat.in","r",stdin);
115     freopen("eat.out","w",stdout);
116     init();
117     work();
118     printf("%d\n",False);
119     return 0;
120 }