1. poj 2139
题意
奶牛们最近要拍电影了……
1、若两个的奶牛一起工作则，他们相互的度（degrees）为；
2、若两只奶牛a、b不一起工作，但与另有一只奶牛都和他们工作，则a、b的相互的度为2。
求奶牛的与其他奶牛的度的平均值的100的整数。
思路
这个题用floyd算法最为合适;
// #include<bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <algorithm>
const int INF = 0x3f3f3f3f;
const int N=310;
int n,d[N][N],c,x,y,m,a[N];
int main(void)
{
// ios::sync_with_stdio(false);
while(~scanf("%d%d",&n,&m)){
memset(d,INF,sizeof(d));
while(m--){
scanf("%d",&c);
for(int i=1;i<=c;i++)
scanf("%d",&a[i]),a[i]--;
for(int i=1;i<=c;i++)
for(int j=1;j<=i;j++)
d[a[i]][a[j]]=d[a[j]][a[i]]=1;
}
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
int ans=INF;
for(int i=0;i<n;i++){
int tmp=0;
for(int j=0;j<n;j++)
if(i!=j) tmp+=d[i][j];
if(tmp<ans) ans=tmp;
}
printf("%d
",100*ans/(n-1));
}
return 0;
}
还在网上看到有两种解法：
dijkstra-邻接矩阵
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 300;
const int INF = 0x3f3f3f3f;
int cost[N+1][N+1];
int d[N+1];
bool v[N+1];
int n;
void input()
{
int m;
cin >> n >> m;
for (int i = 1; i <= n; i ++)
fill(cost[i]+1, cost[i]+1+n, INF);
while ( m-- ) {
int k, movie[N];
cin >> k;
for (int i = 0; i < k; i++) {
scanf("%d", &movie[i]);
}
for (int i = 0; i < k; i++) {
for (int j = i+1; j < k; j++) {
cost[movie[i]][movie[j]] = 1;
cost[movie[j]][movie[i]] = 1;
}
}
}
}
int dijkstra(int s)
{
fill(d+1, d+1+n, INF);
fill(v+1, v+1+n, false);
d[s] = 0;
while ( true ) {
int u = -1;
for (int i = 1; i <= n; i ++) {
if ( !v[i] && ( u == -1 || d[i] < d[u] ) )
u = i;
}
if ( u == -1 )
break;
v[u] = true;
for (int i = 1; i <= n; i ++) {
if ( !v[i] && d[u] + cost[u][i] < d[i] )
d[i] = d[u] + cost[u][i];
}
}
int sum = 0;
for (int i = 1; i <= n; i ++)
sum += d[i];
return sum;
}
void solve()
{
int sum;
int msum = INF;
for (int i = 1; i <= n; i ++) {
sum = dijkstra(i);
msum = (sum < msum) ? sum : msum;
}
double res = (double)msum / (n-1) * 100;
printf("%d
", (int)res);
}
int main(void)
{
input();
solve();
return 0;
}
dijkstra-邻接表
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
const int N = 300;
const int INF = 0x3f3f3f3f;
struct Edge {
int to, cost;
Edge(int t, int c) {
to = t;
cost = c;
}
};
typedef pair<int, int> P;
int n;
int d[N+1];
vector<Edge> G[N+1];
void input()
{
int m;
cin >> n >> m;
while ( m-- ) {
int k, movie[N];
cin >> k;
for (int i = 0; i < k; i++) {
scanf("%d", &movie[i]);
}
for (int i = 0; i < k; i++) {
for (int j = i+1; j < k; j++) {
G[movie[i]].push_back(Edge(movie[j], 1));
G[movie[j]].push_back(Edge(movie[i], 1));
}
}
}
}
int dijkstra(int s) {
priority_queue<P, vector<P>, greater<P> > que;
fill(d+1, d+1+n, INF);
d[s] = 0;
que.push(P(0, s));
while ( !que.empty() ) {
P p = que.top(); que.pop();
int u = p.second;
if (d[u] < p.first) continue;
for (int i = 0; i < G[u].size(); i++) {
Edge e = G[u][i];
if ( d[e.to] > d[u] + e.cost) {
d[e.to] = d[u] + e.cost;
que.push(P(d[e.to], e.to));
}
}
}
int sum = 0;
for (int i = 1; i <= n; i ++)
sum += d[i];
return sum;
}
void solve()
{
int sum;
int msum = INF;
for (int i = 1; i <= n; i ++) {
sum = dijkstra(i);
msum = (sum < msum) ? sum : msum;
}
double res = (double)msum / (n-1) * 100;
printf("%d
", (int)res);
}
int main(void)
{
input();
solve();
return 0;
}
2. poj 3268
题意：有n个农场和m条单向的路 one-way 和每条路通过所要的时间，除X外其他农场的牛都来X农场开party，结束都各自回家，问所有牛各自所花最短时间中 那个最大的时间是多少
思路：dijkstra算法再搞一个反向图
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
#define MAX_V 10240
// 从顶点from指向顶点to的权值为cost的边
struct edge
{
int to, cost;
edge(){}
edge(int to, int cost) : to(to), cost(cost){}
};
// first 最短路径，second顶点编号
typedef pair<int, int> P;
// 图
vector<vector<edge> > G(MAX_V);
// 反向图
vector<vector<edge> > RG(MAX_V);
// 最短距离
int d[MAX_V];
int rd[MAX_V];
// V是顶点数，E是边数
int V, E;
// 求解从顶点s出发到所有点的最短距离
void dijkstra(int s)
{
priority_queue<P, vector<P>, greater<P> > que;
memset(d, 0x3f, sizeof(d));
d[s] = 0;
que.push(P(0, s));
while (!que.empty())
{
P p = que.top(); que.pop();
int v = p.second;
if (d[v] < p.first) continue;
for (int i = 0; i < G[v].size(); ++i)
{
edge e = G[v][i];
if (d[e.to] > d[v] + e.cost)
{
d[e.to] = d[v] + e.cost;
que.push(P(d[e.to], e.to));
}
}
}
}
int main(int argc, char *argv[])
{
int M, X;
cin >> V >> M >> X;
--X;
while (M--)
{
int A, B, T;
cin >> A >> B >> T;
--A;
--B;
G[A].push_back(edge(B, T));
RG[B].push_back(edge(A, T));
}
dijkstra(X);
G = RG;
memcpy(rd, d, sizeof(d));
dijkstra(X);
for (int i = 0; i < V; ++i)
{
d[i] += rd[i];
}
cout << *max_element(d, d + V) << endl;
return 0;
}
3. poj 3259
题意：有n块地，有m个双向路，走双向路需要花费一定时间，有w个单向路，走单向路会让时间倒流一定时间。求是否可以从起点出发再回到起点，在之前从起点开始出发之前到达起点。
思路：bellman_ford。由于存在负权边，Dijkstra便不能用了。题目简化下，就是看图中有没有负权环，有的话可以无限次走这个环，使得时间一定能得到一个负值。所以有的存在负环话就是可以，没有的话就是不可以了。// 其实就是一道检测有无负环的题。
#include<iostream>
#include<string.h>
using namespace std;
const int MAX_N=500+5;
const int MAX_M=5200+5;
typedef struct edge
{
int from;
int to;
int time;
};
edge es[MAX_M];
int n,m,w;
int d[MAX_N];
bool find_negative_loop(int countt)
{
memset(d,1<<26,sizeof(d));
for (int i=0;i<n-1;i++)
{
bool update=false;
for (int j=0;j<countt;j++)
{
edge e=es[j];
if (d[e.to]>d[e.from]+e.time)
{
d[e.to]=d[e.from]+e.time;
update=true;
}
}
if (!update)
break;
}
for (int i=0;i<countt;i++)
{
edge e=es[i];
if (d[e.to]>d[e.from]+e.time)
{
return true;
}
}
return false;
}
int main()
{
int num;
int count;
cin>>num;
while(num--)
{
cin>>n>>m>>w;
int i;
count=0;
for (i=0;i<m;i++)
{
cin>>es[count].from>>es[count].to>>es[count].time;
es[count+1].from=es[count].to;
es[count+1].to=es[count].from;
es[count+1].time=es[count].time;
count+=2;
}
for (;i<m+w;i++)
{
cin>>es[count].from>>es[count].to>>es[count].time;
es[count].time=-es[count].time;
count++;
}
if(find_negative_loop(count))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
4. aoj 2249
题意：要首都（原点）和城市之间修路，有两个要求：1每个城市之间都有一组线连接他们（不用直接相连，这点很重要。）2每个城市和首都的最短路不能动；
Problem H: Road Construction King Mercer is the king of ACM kingdom. There are one capital and some cities in his kingdom. Amazingly, there are no roads in the kingdom now. Recently, he planned to construct roads between the capital and the cities, but it turned out that the construction cost of his plan is much higher than expected. In order to reduce the cost, he has decided to create a new construction plan by removing some roads from the original plan. However, he believes that a new plan should satisfy the following conditions: For every pair of cities, there is a route (a set of roads) connecting them. The minimum distance between the capital and each city does not change from his original plan. Many plans may meet the conditions above, but King Mercer wants to know the plan with minimum cost. Your task is to write a program which reads his original plan and calculates the cost of a new plan with the minimum cost. Input The input consists of several datasets. Each dataset is formatted as follows. N M u1 v1 d1 c1 . . . uM vM dM cM The first line of each dataset begins with two integers, N and M (1 ≤ N ≤ 10000, 0 ≤ M ≤ 20000). N and M indicate the number of cities and the number of roads in the original plan, respectively. The following M lines describe the road information in the original plan. The i-th line contains four integers, ui, vi, di and ci (1 ≤ ui, vi ≤ N , ui ≠ vi , 1 ≤ di ≤ 1000, 1 ≤ ci ≤ 1000). ui , vi, di and ci indicate that there is a road which connects ui-th city and vi-th city, whose length is di and whose cost needed for construction is ci. Each road is bidirectional. No two roads connect the same pair of cities. The 1-st city is the capital in the kingdom. The end of the input is indicated by a line containing two zeros separated by a space. You should not process the line as a dataset. Output For each dataset, print the minimum cost of a plan which satisfies the conditions in a line. Sample Input 3 3 1 2 1 2 2 3 2 1 3 1 3 2 5 5 1 2 2 2 2 3 1 1 1 4 1 1 4 5 1 1 5 3 1 1 5 10 1 2 32 10 1 3 43 43 1 4 12 52 1 5 84 23 2 3 58 42 2 4 86 99 2 5 57 83 3 4 11 32 3 5 75 21 4 5 23 43 5 10 1 2 1 53 1 3 1 65 1 4 1 24 1 5 1 76 2 3 1 19 2 4 1 46 2 5 1 25 3 4 1 13 3 5 1 65 4 5 1 34 0 0 Output for the Sample Input 3 5 137 218
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 20000+5
#define P pair<int,int> //first最短路径second顶点编号
using namespace std;
int N,M;
struct edge
{
int to,dis,cost;
edge(int to,int dis,int cost):to(to),dis(dis),cost(cost) {}
};
vector<edge> G[Maxn];//G[i] 从i到G[i].to的距离为dis，花费的钱为cost
int d[Maxn][Maxn];//d[i][j]从i到j的最短距离
int sum[Maxn];//sum[i]，起点到i之间所需要的花费的钱
void Dijk(int s)
{
priority_queue<P,vector<P>,greater<P> >q;//按first从小到大出队
for(int i=0; i<=N; i++)
d[s][i]=INF;
d[s][s]=0;
q.push(P(0,s));
while(!q.empty())
{
P p=q.top();
q.pop();
int v=p.second;//点v
if(d[s][v]<p.first)
continue;
for(int i=0; i<G[v].size(); i++)
{
edge e=G[v][i];//枚举与v相邻的点
if(d[s][e.to]>=d[s][v]+e.dis)
{
if(d[s][e.to]==d[s][v]+e.dis)//距离相等，比较谁花费的钱少
sum[e.to]=min(sum[e.to],e.cost);
else//若d[s][e.to]>d[s][v]+e.dis，相求出最短距离，再求出最短距离所需要的钱
sum[e.to]=e.cost;
d[s][e.to]=d[s][v]+e.dis;
q.push(P(d[s][e.to],e.to));
}
}
}
}
int main()
{
IOS;
while(cin>>N>>M,N+M)
{
MEM(sum,0);
for(int i=1; i<=N; i++)
G[i].clear();
for(int i=0; i<M; i++)
{
int u,v,d,c;
cin>>u>>v>>d>>c;
G[u].push_back(edge(v,d,c));
G[v].push_back(edge(u,d,c));
}
Dijk(1);//城市1到各个城市的最短距离
int ans=0;
for(int i=2; i<=N; i++)
ans+=sum[i];
cout<<ans<<endl;
}
return 0;
}
5. aoj 2200
快递到了：你是某个岛国（ACM-ICPC Japan）上的一个苦逼程序员，你有一个当邮递员的好基友利腾桑遇到麻烦了：全岛有一些镇子通过水路和旱路相连，走水路必须要用船，在X处下船了船就停在X处。而且岛上只有一条船，下次想走水路还是得回到X处才行；两个镇子之间可能有两条以上的水路或旱路；邮递员必须按照清单上的镇子顺序送快递（镇子可能重复，并且对于重复的镇子不允许一次性处理，比如ABCB的话B一定要按顺序走两次才行）。 测试数据有多组： N M x1 y1 t1 sl1 x2 y2 t2 sl2 … xM yM tM slM R z1 z2 … zR N (2 ≤ N ≤ 200) 是镇子的数量，M (1 ≤ M ≤ 10000) 是旱路和水路合计的数量。从第2行到第M + 1行是路径的描述，路径连接xi yi两地，路径花费 ti (1 ≤ ti ≤ 1000)时间，sli 为L时表示是旱路，S时表示是水路。可能有两条及以上路径连接两个镇子，并且路径都是双向的。 M + 2行的R是利腾需要去的镇子的数量，M + 3是利腾需要去的镇子的编号。 初始状态利腾和船都在第一个镇子，且肯定有方法达到需要去的镇子。 测试数据为0 0的时候表示终止。 输出量 对于每个输入数据集，请找到Rito先生在给定的提取和交付顺序中访问城镇所需的最短旅行时间，并将其输出一行。 样本输入 3 3 1 2 5 L 1 2 7 S 2 3 11 S 3 1 2 3 5 5 1 2 15 L 2 3 10 L 4 5 7 L 1 3 30 S 3 4 100 S 5 1 3 5 4 1 0 0 样本输入的输出 18 269
#include <cstdio>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#define min(a,b) (((a) < (b)) ? (a) : (b))
#define max(a,b) (((a) > (b)) ? (a) : (b))
#define abs(x) ((x) < 0 ? -(x) : (x))
//#define INF 0x3f3f3f3f
#define delta 0.85
#define eps 1e-3
#define PI 3.14159265358979323846
#define MAX_V 205
#define MAX_R 1005
using namespace std;
const int INF = 1e8; //0x3f3f3f3f * 3 则 int 溢出
int E, V, R;
int order[MAX_R];
int dl[MAX_V][MAX_V], ds[MAX_V][MAX_V], dp[MAX_R][MAX_V];
int main(){
while(~scanf("%d%d", &V, &E) && V){
for(int i = 0; i < V; i++){
for(int j = 0; j < V; j++){
dl[i][j] = ds[i][j] = INF;
}
dl[i][i] = ds[i][i] = 0;
}
for(int i = 0; i < E; i++){
char c;
int u, v, d;
scanf("%d%d%d %c", &u, &v, &d, &c);
--u, --v;
if(c == 'L') dl[u][v] = dl[v][u] = min(dl[u][v], d);
else ds[u][v] = ds[v][u] = min(ds[u][v], d);
}
scanf("%d", &R);
for(int i = 0; i < R; i++){
scanf("%d", order + i);
--order[i];
}
// Warshall_floyd
for(int k = 0; k < V; k++){
for(int i = 0; i < V; i++){
for(int j = 0; j < V; j++){
dl[i][j] = min(dl[i][j], dl[i][k] + dl[k][j]);
ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j]);
}
}
}
// Dp
for (int i = 0; i < R; i++){
for(int j = 0; j < V; j++){
dp[i][j] = INF;
}
}
dp[0][order[0]] = 0;
for(int i = 0; i < R - 1; i++){
for(int j = 0; j < V; j++){
if(dp[i][j] != INF){
// 直接走陆路
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + dl[order[i]][order[i + 1]]);
for(int k = 0; k < V; k++){
// 陆路-海路-陆路
dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + dl[order[i]][j] + ds[j][k] + dl[k][order[i + 1]]);
}
}
}
}
printf("%d
", *min_element(dp[R - 1], dp[R - 1] + V));
}
return 0;
}