Floyed应用---多源最短路优化

vijos P1046 最小环

无向图求最小环因为数据很小，所以弗洛伊德算法就可以了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#include<cmath>
#define INF 100000000
using namespace std;

int n,m,ans,z,x,y;
int d[105][105],a[105][105];

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        for(int i = 1;i <= n; ++i)
            for(int j = 1;j <= n; ++j)
                d[i][j] = a[i][j] = INF;
        ans = INF;
        for(int i = 1;i <= m; ++i)
        {
            scanf("%d%d%d",&x,&y,&z);
            a[x][y] = a[y][x] = d[x][y] = d[y][x] = min(z , a[x][y]);
        }
        for(int k = 1;k <= n; ++k)
        {
            for(int i = 1;i < k; ++i)
                for(int j = i + 1;j < k; ++j)
                {
                    ans = min(ans , d[i][j] + a[i][k] + a[k][j]);
                }
            for(int i = 1;i <= n; ++i)
                for(int j = 1;j <= n; ++j)
                    if(d[i][j] > d[i][k] + d[k][j])
                        d[i][j] = d[j][i] = d[i][k] + d[k][j];
        }
        if(ans < INF) printf("%d\n",ans);
        else printf("No solution.\n");
    }
    return 0;
}

FZU - 2271

求无向图中可以删除一些边，使得任意两点的最短路不改变，求这些边能删除的最大的条数解： 1 输入时去掉重边，保留最小边 2 如果原来两点的最短距离大于经过第三个点的最短距离（可以松弛），将这条边替换成经过第三个点的边，删除原来的边

3 如果两点之间本来没有边直接continue

#include<bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;
int T,n,m,ans;
int f[110][110];
bool vis[110][110];

int main()
{
    scanf("%d",&T);
    for(int tot = 1;tot <= T; ++tot)
    {
        scanf("%d%d",&n,&m);
        for(int i = 1;i <= n; ++i)
            for(int j = 1;j <= n; ++j)
                f[i][j] = inf,vis[i][j] = 0;
        for(int i = 0;i < m; ++i)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            f[x][y] = f[y][x] = min(f[x][y],z);
        }
        for(int k = 1;k <= n; ++k)
            for(int i = 1;i <= n; ++i)
                for(int j = 1;j <= n; ++j)
                    if(f[i][j] >= f[i][k] + f[k][j])
                        f[i][j] = f[i][k] + f[k][j],vis[i][j] = 1;
        ans = 0;
        for(int i = 1;i <= n; ++i)
            for(int j = 1;j <= n; ++j)
                if(!vis[i][j] && f[i][j] != inf) ans++;
        ans = m - ans / 2;
        printf("Case %d: %d\n",tot,ans);
    }
    return 0;
}

Minimum Transport Cost

HDU - 1385 记录路径 + 注意经过每个点都会有一个代价（路径=路现长+经过点代价） + 路径字典序最小

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAX = 250;
int a[MAX][MAX],N,n,m;
int path[MAX][MAX],b[MAX];

void Printf(int n,int m)
{
	int k;
	printf("From %d to %d :\n",n,m);
	printf("Path: %d",n);
	k = n;
	while(k != m)
	{
		printf("-->%d",path[k][m]);
		k = path[k][m];
	}
	printf("\nTotal cost : %d\n\n",a[n][m]);
}

void floyd()
{
	int len;
	for(int k = 1;k <= N; ++k)
        for(int i = 1;i <= N; ++i)
            for(int j = 1;j <= N; ++j)
            {
                len = a[i][k]+b[k]+a[k][j];//在中间增加一个k
                if(a[i][j]>len)//找到一条更短路则更新
                {
                    a[i][j] = len;
                    path[i][j] = path[i][k];
                }
                else if(len==a[i][j])//当相等值时，找字典序最小的，只要比较前一个就行了
                    path[i][j] = min(path[i][k],path[i][j]);
            }
}

int main()
{
	while(scanf("%d",&N))
	{
	    if(!N) break;
		for(int i = 1;i <= N; ++i)
			for(int j = 1;j <= N; ++j)
			{
				scanf("%d",&a[i][j]);
				if(a[i][j] == -1) a[i][j] = INF;
				if(i == j) a[i][j] = 0;
				path[i][j] = j;
			}
		for(int i = 1;i <= N; ++i) scanf("%d",&b[i]);
		floyd();
		while(scanf("%d%d",&n,&m)&&(n!=-1&&m!=-1))
		{
		    if(n == -1 && m == -1) break;
			if(n == m)
			{
				printf("From %d to %d :\n",n,m);
				printf("Path: %d",n);
				printf("\nTotal cost : 0\n\n");
			}
			else
			Printf(n,m);
		}
	}
	return 0;
}

Ranking the Cows

POJ - 3275

大意： n头牛，m个关系，问还需要知道多少关系使得所有牛的排名都被确定

floyed后一共需要有n*(n-1)/2条边，减去已经有的边

n = 1000 有点大，可以用bitset/邻接表优化

#include<iostream>
#include<cmath>
#include<bitset>
#include<cstring>
#include<string>
#include<cstdio>
using namespace std;

int n,m,ans,x,y;
bitset<1010>b[1010];

int main()
{
    scanf("%d%d",&n,&m);
    memset(b,0,sizeof(b));
    for(int i = 0;i < m;++i)
    {
        scanf("%d%d",&x,&y);
        b[x][y] = 1;
    }
    for(int i = 1;i <= n; ++i)
        for(int j = 1;j <= n; ++j)
            if(b[j][i]) b[j] |= b[i];
    ans = 0;
    for(int i = 1;i <= n; ++i)
        for(int j = 1;j <= n; ++j)
            if(b[i][j]) ans++;
    ans = n * (n - 1) / 2 - ans;
    printf("%d\n",ans);
    return 0;
}

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e3+5;
vector<int>from[N],to[N];
bool mp[N][N];
int n,m,ans,u,v;

void init()
{
    memset(mp,false,sizeof(mp));
    for(int i=1;i<=n;i++)
    {
        from[i].clear();
        to[i].clear();
    }
}
void add(int u,int v)
{
    mp[u][v]=1;
    from[v].push_back(u),to[u].push_back(v);
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        for(int i = 1;i <= m;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,v);
        }
        for(int k = 1;k <= n;k++)
            for(int i = 0;i < from[k].size();i++)   //能够直接到达k的点
                for(int j = 0;j < to[k].size();j++)
                {    //能够由k直接到达的点    
                    int u = from[k][i],v = to[k][j];
                    if(!mp[u][v])add(u,v);    //只用更新那些没有传递关系的点
                }
        ans = 0;
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++)
                if(mp[i][j]) ans++;
        printf("%d\n",n * (n - 1) / 2 - ans);
    }
}

Floyed应用---多源最短路 优化

Minimum Transport Cost

Ranking the Cows

Floyed应用---多源最短路优化