第二讲：图论

• 图：

1. 点&边
2.  边的权 点的度（出入度）

•  存储：

1. 矩阵
2.   邻接表（往头部插才为o(1)  稀疏图 练习链表）Dfs bfs
3.   邻接多重表
4.   十字链表
5.  强连通子图（有向图）：任意两点都有路径（两项）dfs 缩点

•  生成树问题：1.无向图：

1.     prim算法：点少
2.     kruskal算法：边少
3.     spaf算法
4.     dijkstar算法
5.     环属性
6.     剪切属性
7.     最小边原则
8.     唯一性

 

 

测试：

题目：

Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollar. Then, by converting currencies, a clever trader can start with 1 US dollar and buy 0.5 * 10.0 * 0.21 = 1.05 US dollars, making a profit of 5 percent.

Your job is to write a program that takes a list of currency exchange rates as input and then determines whether arbitrage is possible or not.

Input

The input will contain one or more test cases. Om the first line of each test case there is an integer n (1<=n<=30), representing the number of different currencies. The next n lines each contain the name of one currency. Within a name no spaces will appear. The next line contains one integer m, representing the length of the table to follow. The last m lines each contain the name ci of a source currency, a real number rij which represents the exchange rate from ci to cj and a name cj of the destination currency. Exchanges which do not appear in the table are impossible.
Test cases are separated from each other by a blank line. Input is terminated by a value of zero (0) for n.

Output

For each test case, print one line telling whether arbitrage is possible or not in the format "Case case: Yes" respectively "Case case: No".

Sample Input

3
USDollar
BritishPound
FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar

3
USDollar
BritishPound
FrenchFranc
6
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar

0

Sample Output

Case 1: Yes
Case 2: No
题解：floyd可做，f[M][M]的清零，注意long long的%lld,用char数组要用strcmp进行比较！对大于小于的理解！！
爱吃代码：

#include<cstdio>
#include<cstring>
#define esp 0.000001
#define M 500
using namespace std;
int n,m,bb,cc,cs,tmp;
double f[M][M],x;
char b[M],c[M],a[M][M];
int main()
{
    while(~scanf("%d",&n))
    {
        cs++;
        if(n==0)
            break;
        for(int i=0;i<n;i++)
        {
            scanf("%s",a[i]);
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
                f[i][j]=0.0;
        }
        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {
            scanf("%s%lf%s",b,&x,c);
            for(int i=0;i<n;i++)
            {
                if(strcmp(b,a[i])==0)
                    bb=i;
                if(strcmp(c,a[i])==0)
                    cc=i;
            }
            f[bb][cc]=x;
        }
        /*for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
                printf(" %lf 
",f[i][j]);
        }*/
        for(int k=0;k<n;k++)
        {
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    if(f[i][k]*f[k][j]>f[i][j])
                        f[i][j]=f[i][k]*f[k][j];

                }
            }
        }
        //printf("
");
        tmp=0;
        for(int i=0;i<n;i++)
        {
           //printf(" %lf ",f[i][i]);
            if(f[i][i]-1>esp)
            {
                printf("Case %d: Yes
",cs);
                tmp=1;
                break;
            }

        }
        if(tmp==0)
            printf("Case %d: No
",cs);

    }
    return 0;
}

2.

经过锦囊相助，海东集团终于度过了危机，从此，HDU的发展就一直顺风顺水，到了2050年，集团已经相当规模了，据说进入了钱江肉丝经济开发区500强。这时候，XHD夫妇也退居了二线，并在风景秀美的诸暨市浬浦镇陶姚村买了个房子，开始安度晚年了。
这样住了一段时间，徐总对当地的交通还是不太了解。有时很郁闷，想去一个地方又不知道应该乘什么公交车，在什么地方转车，在什么地方下车（其实徐总自己有车，却一定要与民同乐，这就是徐总的性格）。
徐总经常会问蹩脚的英文问路：“Can you help me?”。看着他那迷茫而又无助的眼神，热心的你能帮帮他吗？
请帮助他用最短的时间到达目的地（假设每一路公交车都只在起点站和终点站停，而且随时都会开）。

Input输入数据有多组，每组的第一行是公交车的总数N(0<=N<=10000)；
第二行有徐总的所在地start，他的目的地end；
接着有n行，每行有站名s，站名e，以及从s到e的时间整数t(0<t<100)(每个地名是一个长度不超过30的字符串)。
note：一组数据中地名数不会超过150个。
如果N==-1，表示输入结束。
Output如果徐总能到达目的地，输出最短的时间；否则，输出“-1”。
Sample Input

6
xiasha westlake
xiasha station 60
xiasha ShoppingCenterofHangZhou 30
station westlake 20
ShoppingCenterofHangZhou supermarket 10
xiasha supermarket 50
supermarket westlake 10
-1

Sample Output

50


Hint:
The best route is:
xiasha->ShoppingCenterofHangZhou->supermarket->westlake


虽然偶尔会迷路，但是因为有了你的帮助
**和**从此还是过上了幸福的生活。

――全剧终――
题解：要用map（映射）去存字符串！，注意格式和清零！！！cnt now ans 清零，a，b不要写反！m，n不要写反！！！
爱吃代码：

#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#define inf 0x3f3f
#define M 300
using namespace std;
int n,f[M][M],aa,bb,ss,tt,w,cnt;
char vis[M][M],a[M],b[M],s[M],t[M];
map<string,int>m;
int main()
{
    while(~scanf("%d",&n))
    {
        if(n==-1)
            break;
        cnt=1;
        m.clear();
        scanf("%s%s",s,t);
        if(strcmp(s,t)==0)
            m[s]=m[t]=cnt++;
        else
        {
            m[s]=cnt++;
            m[t]=cnt++;
        }
        ss=m[s];
        tt=m[t];
        for(int i=0;i<200;i++)
            for(int j=0;j<200;j++)
            {
                if(i==j)
                    f[i][j]=0;
                else f[i][j]=inf;
            }

        for(int i=0;i<n;i++)
        {
            scanf("%s%s%d",a,b,&w);
            /*
            aa=-1;
            bb=-1;
            for(int j=0;j<155;j++)
            {
                if(strcmp(a,vis[j])==0)
                    aa=j;
                if(strcmp(b,vis[j])==0)
                    bb=j;
            }

            if(aa<0)
            {
                aa=cnt;
                strcpy(vis[cnt++],a);
            }
            if(bb<0)
            {
                bb=cnt;
                strcpy(vis[cnt++],b);
            }*/
            if(!m[a]) m[a]=cnt++;
            if(!m[b]) m[b]=cnt++;
            if(w<f[m[a]][m[b]])
                f[m[a]][m[b]]=f[m[b]][m[a]]=w;
        }
        for(int k=1;k<=cnt;k++)
        {
            for(int i=1;i<=cnt;i++)
            {
                for(int j=1;j<=cnt;j++)
                {
                    if(f[i][k]+f[k][j]<f[i][j])
                        f[i][j]=f[i][k]+f[k][j];
                }
            }
        }
        if(ss==tt)
            printf("0
");
        else if(f[ss][tt]<inf)
            printf("%d
",f[ss][tt]);

        else
            printf("-1
");
    }
    return 0;
}

3.

In the age of television, not many people attend theater performances. Antique Comedians of Malidinesia are aware of this fact. They want to propagate theater and, most of all, Antique Comedies. They have printed invitation cards with all the necessary information and with the programme. A lot of students were hired to distribute these invitations among the people. Each student volunteer has assigned exactly one bus stop and he or she stays there the whole day and gives invitation to people travelling by bus. A special course was taken where students learned how to influence people and what is the difference between influencing and robbery.
The transport system is very special: all lines are unidirectional and connect exactly two stops. Buses leave the originating stop with passangers each half an hour. After reaching the destination stop they return empty to the originating stop, where they wait until the next full half an hour, e.g. X:00 or X:30, where 'X' denotes the hour. The fee for transport between two stops is given by special tables and is payable on the spot. The lines are planned in such a way, that each round trip (i.e. a journey starting and finishing at the same stop) passes through a Central Checkpoint Stop (CCS) where each passenger has to pass a thorough check including body scan.

All the ACM student members leave the CCS each morning. Each volunteer is to move to one predetermined stop to invite passengers. There are as many volunteers as stops. At the end of the day, all students travel back to CCS. You are to write a computer program that helps ACM to minimize the amount of money to pay every day for the transport of their employees.

InputThe input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case begins with a line containing exactly two integers P and Q, 1 <= P,Q <= 1000000. P is the number of stops including CCS and Q the number of bus lines. Then there are Q lines, each describing one bus line. Each of the lines contains exactly three numbers - the originating stop, the destination stop and the price. The CCS is designated by number 1. Prices are positive integers the sum of which is smaller than 1000000000. You can also assume it is always possible to get from any stop to any other stop.
OutputFor each case, print one line containing the minimum amount of money to be paid each day by ACM for the travel costs of its volunteers.
Sample Input

2
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

Sample Output

46
210
题解：又一道de了很久很久的bug，思路很重要，先正着存，然后spfa从1出发，然后算出所用的dis【i】，然后再倒着存，还是从1出发算dis【i】
注意：inf的值也不易太大，如果太大要超出，cnt要从1开始，省的每次都有错，spfa注意dis【x】=0，注意n，m的区别；
爱吃代码：

#include<cstdio>
#include<queue>
#define inf 1e8
#define M 2001000
using namespace std;
long long cnt=1,n,m,u[M],v[M],w[M],head[M],dis[M],t,ans,vis[M];
struct hhh
{
    long long to,nxt,w;
}e[M];
queue<long long >q;
void add(long long u,long long v,long long w)
{
    e[cnt].to=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt++;
}
void spaf(int x)
{
    for(int i=0;i<=n;i++)
    {
        if(x==i)
            dis[i]=0;
        else dis[i]=inf;
    }
    //printf("a%da ",dis[1]);
    vis[x]=1;
    q.push(x);
    int r,v;
    while(!q.empty())
    {
        r=q.front();
        q.pop();
        for(int i=head[r];i;i=e[i].nxt)
        {
            v=e[i].to;
            if(dis[v]>dis[r]+e[i].w)
            {
                dis[v]=dis[r]+e[i].w;
                //printf("aaa");
                if(vis[v]==0)
                    vis[v]=1,q.push(v);
            }
        }
        vis[r]=0;
    }

}
int main()
{
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%lld",&n,&m);
        cnt=1;
        for(int i=0;i<=n;i++)
        {
            head[i]=0,e[i].to=e[i].nxt=e[i].w=0;
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%lld%lld%lld",&u[i],&v[i],&w[i]);
            add(u[i],v[i],w[i]);
        }
        ans=0;
        spaf(1);
        for(int i=1;i<=n;i++)
        {
            ans+=dis[i];
        }
        //printf(" %d ",ans);
        for(int i=0;i<=m;i++)
        {
            head[i]=0;
        }
        cnt=1;
        for(int i=1;i<=m;i++)
        {
           add(v[i],u[i],w[i]);
        }
        spaf(1);
        for(int i=1;i<=n;i++)
        {
            ans+=dis[i];
        }
        printf("%lld
",ans);
    }
    return 0;
}

4.

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. The maximal pseudoforests of G are the pseudoforest subgraphs of G that are not contained within any larger pseudoforest of G. A pesudoforest is larger than another if and only if the total value of the edges is greater than another one’s.

InputThe input consists of multiple test cases. The first line of each test case contains two integers, n(0 < n <= 10000), m(0 <= m <= 100000), which are the number of the vertexes and the number of the edges. The next m lines, each line consists of three integers, u, v, c, which means there is an edge with value c (0 < c <= 10000) between u and v. You can assume that there are no loop and no multiple edges.
The last test case is followed by a line containing two zeros, which means the end of the input.
OutputOutput the sum of the value of the edges of the maximum pesudoforest.
Sample Input

3 3
0 1 1
1 2 1
2 0 1
4 5
0 1 1
1 2 1
2 3 1
3 0 1
0 2 2
0 0

Sample Output

3
5
不会
5.

Given a connected undirected graph, tell if its minimum spanning tree is unique.

Definition 1 (Spanning Tree): Consider a connected, undirected graph G = (V, E). A spanning tree of G is a subgraph of G, say T = (V', E'), with the following properties:
1. V' = V.
2. T is connected and acyclic.

Definition 2 (Minimum Spanning Tree): Consider an edge-weighted, connected, undirected graph G = (V, E). The minimum spanning tree T = (V, E') of G is the spanning tree that has the smallest total cost. The total cost of T means the sum of the weights on all the edges in E'.

Input

The first line contains a single integer t (1 <= t <= 20), the number of test cases. Each case represents a graph. It begins with a line containing two integers n and m (1 <= n <= 100), the number of nodes and edges. Each of the following m lines contains a triple (xi, yi, wi), indicating that xi and yi are connected by an edge with weight = wi. For any two nodes, there is at most one edge connecting them.

Output

For each input, if the MST is unique, print the total cost of it, or otherwise print the string 'Not Unique!'.

Sample Input

2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2

Sample Output

3
Not Unique!
题解：最小生成树，然后是唯一的，记录有哪些路径在最小生成树中，然后for不要其中一条去看是否可以形成值相同的最小生成树；
注意：ans cnt 清零，特判n==1&&m==0 跑两趟 区分m和n
爱吃代码

#include<cstdio>
#include<algorithm>
#define M 1020
#define N 10100
using namespace std;
int t,n,m,a,b,c,ww,ans,fa[M],cnt,aa,now,q,no,vis[M],ans1,ans2;
struct hhh
{
    int f,to,w;
}e[N];
int finda(int x)
{
    if(x==fa[x]) return x;
    return fa[x]=finda(fa[x]);
}
bool cmp(hhh a,hhh b)
{
    if(a.w==b.w) return a.to<b.to;
    return a.w<b.w;
}
int kruskal()
{
    for(int i=0;i<=n;i++)
        fa[i]=i;
    ans=0;
    cnt=0;
    for(int i=1;i<=m;i++)
    {
        a=finda(e[i].f);
        b=finda(e[i].to);
        if(a==b) continue;
        if(q==0 && i==no) continue;
        ww=e[i].w;
        ans+=ww;
        fa[a]=b;
        cnt++;
        if(q==1) vis[now++]=i;
        if(cnt==n-1) break;
    }
    if(cnt==n-1) return ans;
    return -1;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        aa=1;
        now=0;
        for(int i=0;i<=n;i++)
            fa[i]=i;
        for(int i=1;i<=m;i++)
            scanf("%d%d%d",&e[i].f,&e[i].to,&e[i].w);
        sort(e+1,e+m+1,cmp);
        q=1;
        ans1=kruskal();
        if(ans1==-1) ans1=0;
        q=0;
        for(int i=0;i<now;i++)
        {
            no=vis[i];
            ans2=kruskal();
            if(ans2==ans1) aa=0;
        }
        if(n==1 || m==0)
            printf("0
");
        else if(aa==1)
           printf("%d
",ans1);
        else printf("Not Unique!
");
    }
    return 0;
}

6.

Marica is very angry with Mirko because he found a new girlfriend and she seeks revenge.Since she doesn't live in the same city, she started preparing for the long journey.We know for every road how many minutes it takes to come from one city to another.
Mirko overheard in the car that one of the roads is under repairs, and that it is blocked, but didn't konw exactly which road. It is possible to come from Marica's city to Mirko's no matter which road is closed.
Marica will travel only by non-blocked roads, and she will travel by shortest route. Mirko wants to know how long will it take for her to get to his city in the worst case, so that he could make sure that his girlfriend is out of town for long enough.Write a program that helps Mirko in finding out what is the longest time in minutes it could take for Marica to come by shortest route by non-blocked roads to his city.

InputEach case there are two numbers in the first row, N and M, separated by a single space, the number of towns,and the number of roads between the towns. 1 ≤ N ≤ 1000, 1 ≤ M ≤ N*(N-1)/2. The cities are markedwith numbers from 1 to N, Mirko is located in city 1, and Marica in city N.
In the next M lines are three numbers A, B and V, separated by commas. 1 ≤ A,B ≤ N, 1 ≤ V ≤ 1000.Those numbers mean that there is a two-way road between cities A and B, and that it is crossable in V minutes.OutputIn the first line of the output file write the maximum time in minutes, it could take Marica to come to Mirko.Sample Input

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

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

5 7
1 2 8
1 4 10
2 3 9
2 4 10
2 5 1
3 4 7
3 5 10
不会
7.

年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币，便请求酋长降低要求。酋长说："嗯，如果你能够替我弄到大祭司的皮袄，我可以只要8000金币。如果你能够弄来他的水晶球，那么只要5000金币就行了。"探险家就跑到大祭司那里，向他要求皮袄或水晶球，大祭司要他用金币来换，或者替他弄来其他的东西，他可以降低价格。探险家于是又跑到其他地方，其他人也提出了类似的要求，或者直接用金币换，或者找到其他东西就可以降低价格。不过探险家没必要用多样东西去换一样东西，因为不会得到更低的价格。探险家现在很需要你的帮忙，让他用最少的金币娶到自己的心上人。另外他要告诉你的是，在这个部落里，等级观念十分森严。地位差距超过一定限制的两个人之间不会进行任何形式的直接接触，包括交易。他是一个外来人，所以可以不受这些限制。但是如果他和某个地位较低的人进行了交易，地位较高的的人不会再和他交易，他们认为这样等于是间接接触，反过来也一样。因此你需要在考虑所有的情况以后给他提供一个最好的方案。
为了方便起见，我们把所有的物品从1开始进行编号，酋长的允诺也看作一个物品，并且编号总是1。每个物品都有对应的价格P，主人的地位等级L，以及一系列的替代品Ti和该替代品所对应的"优惠"Vi。如果两人地位等级差距超过了M，就不能"间接交易"。你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。

Input

输入第一行是两个整数M，N（1 <= N <= 100），依次表示地位等级差距限制和物品的总数。接下来按照编号从小到大依次给出了N个物品的描述。每个物品的描述开头是三个非负整数P、L、X（X < N），依次表示该物品的价格、主人的地位等级和替代品总数。接下来X行每行包括两个整数T和V，分别表示替代品的编号和"优惠价格"。

Output

输出最少需要的金币数。

Sample Input

1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 0

Sample Output

5250
不会
8.

It's now the year 21XX,when the earth will explode soon.The evil U.S. decided to invade the Mars to save their lives.
But the childlike Marsmen never keeps any army,because war never take place on the Mars.So it's very convenient for the U.S. to act the action.
Luckily,the Marsmen find out the evil plan before the invadation,so they formed a defense system.The system provides enchantment for some citys,and the enchantment generator for city A maybe set in city B,and to make things worse,both city B and C and more will provide echantment for city A.
The satelite of U.S. has got the map of the Mars.And they knows that when they enter a city,they can destory all echantment generator in this city at once,and they can enter a city only if they has destoryed all enchantment generator for this city,but troops can stay at the outside of the city and can enter it at the moment its echantment is destoryed.Of course the U.S. army will face no resistance because the Mars keep no army,so troops can invade in many way at the same time.
Now the U.S. will invade the Mars,give you the map,your task is to calculate the minimium time to enter the capital of the Mars.

InputThe first line contains an integer T,which is the number of test cases. 

For each testcase: 

The first line contains two integers N and M,1<=N<=3000,1<=M<=70000,the cities is numbered from 1 to N and the U.S. landed on city 1 while the capital of the Mars is city N. 

The next M lines describes M paths on the Mars.Each line contains three integers ai,bi and wi,indicates there is a unidirectional path form ai to bi lasts wi minutes(1<=wi<=10^8). 

The next N lines describes N citys,the 1+M+i line starts with a integer li,followed with li integers, which is the number of cities has a echantment generator protects city i. 

It's guaranteed that the city N will be always reachable.OutputFor each case,print a line with a number indicating the minimium time needed to enter the capital of the Mars.Sample Input

1
6 6
1 2 1
1 4 3
2 3 1
2 5 2
4 6 2
5 3 2
0
0
0
1 3
0
2 3 5

Sample Output

5


        
 

Hint

The Map is like this:
We can follow these ways to achieve the fastest speed:
1->2->3,1->2->5,1->4->6.

不会
9.

During the Warring States Period of ancient China(476 BC to 221 BC), there were seven kingdoms in China ---- they were Qi, Chu, Yan, Han, Zhao, Wei and Qin. Ying Zheng was the king of the kingdom Qin. Through 9 years of wars, he finally conquered all six other kingdoms and became the first emperor of a unified China in 221 BC. That was Qin dynasty ---- the first imperial dynasty of China(not to be confused with the Qing Dynasty, the last dynasty of China). So Ying Zheng named himself "Qin Shi Huang" because "Shi Huang" means "the first emperor" in Chinese.

Qin Shi Huang undertook gigantic projects, including the first version of the Great Wall of China, the now famous city-sized mausoleum guarded by a life-sized Terracotta Army, and a massive national road system. There is a story about the road system:
There were n cities in China and Qin Shi Huang wanted them all be connected by n-1 roads, in order that he could go to every city from the capital city Xianyang.
Although Qin Shi Huang was a tyrant, he wanted the total length of all roads to be minimum,so that the road system may not cost too many people's life. A daoshi (some kind of monk) named Xu Fu told Qin Shi Huang that he could build a road by magic and that magic road would cost no money and no labor. But Xu Fu could only build ONE magic road for Qin Shi Huang. So Qin Shi Huang had to decide where to build the magic road. Qin Shi Huang wanted the total length of all none magic roads to be as small as possible, but Xu Fu wanted the magic road to benefit as many people as possible ---- So Qin Shi Huang decided that the value of A/B (the ratio of A to B) must be the maximum, which A is the total population of the two cites connected by the magic road, and B is the total length of none magic roads.
Would you help Qin Shi Huang?
A city can be considered as a point, and a road can be considered as a line segment connecting two points.

InputThe first line contains an integer t meaning that there are t test cases(t <= 10). 

For each test case: 

The first line is an integer n meaning that there are n cities(2 < n <= 1000). 

Then n lines follow. Each line contains three integers X, Y and P ( 0 <= X, Y <= 1000, 0 < P < 100000). (X, Y) is the coordinate of a city and P is the population of that city. 

It is guaranteed that each city has a distinct location.OutputFor each test case, print a line indicating the above mentioned maximum ratio A/B. The result should be rounded to 2 digits after decimal point.Sample Input

2
4
1 1 20
1 2 30
200 2 80
200 1 100
3
1 1 20
1 2 30
2 2 40

Sample Output

65.00
70.00
不会