问题 A: 高速

时间限制: 1 Sec 内存限制: 128 MB
提交: 15 解决: 4
[提交][状态][讨论版][命题人:qianyouyou]

题目描述

教练开车去东北，因为比赛地点在东北。共有 n 座城，已知教练在 s 城，比赛地点在 t 城，n 座城之间共有 m 条高速，每条高速连接两座城市，每两座城市之间最多两条高速。每条高速都有权值 v，表示两个城市之间最快可以 v 小时到达。

然而高速不是永久开放的，每条高速都会有一段开放时间 [ a，b ]，表示该高速在 a ~ b 小时范围之间开放，其余时间处于关闭状态，不能通过任何车辆。例如 [ 24，27 ]表示该路在第 24 小时到 27 小时之间开放。

已知教练在 0 时刻出发，他最快多少小时可以到达 t 城。

（PS：由于刹车坏掉了，因此车一旦启动就不能停下来，也就是说车不能停于某点或某边，不过车可以来回无限次在两地之间穿梭）

输入

多组测试样例，首行输入 t，表示 t 组样例。

图为无向图，s 城固定为 1 点，t 城固定为 n 点。

每组样例第 1 行，输入n，m（1 < n ≤ 100，0 < m ≤ 1000）。

接下来 m 行，每行 5 个数值x，y，v，l，f。表示 x 与 y 有一条高速，耗时为 v。该路开放时间为[ l，f ]。

数据保证教练可以到达终点，只不过是时间问题。

输出

输出一个数值，即最少耗时。

样例输入

样例输出

tag：图论、分时最短路

//最短路
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 0x3f3f3f3f;
const int maxn = 1e5+7;
int t,n,m,cnt;
int dis[maxn];  //当前该点到原点最短距离
bool vis[maxn]; //是否访问过
int head[maxn]; //点集
struct EDGE{
    int next,to,w,l,r;  //上一条边，下一个点，权值，左值，右值
}edge[2*maxn];  //边集
struct NODE{
    int u,dis;
    NODE(){}
	NODE(int u,ll w):u(u),dis(w){}
	bool operator <(const NODE &a)const{
		return dis>a.dis;
	}
}node[2*maxn];  //点集加最短距离
void add(int u, int v, int w, int l,int r){ //构建边集
    edge[cnt].next = head[u];
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].l = l;
    edge[cnt].r = r;
    head[u] = cnt;
    cnt++;
}
void init(){    //初始化
    cnt = 0;
    memset(head,-1,sizeof(head));
    memset(dis,maxx,sizeof(dis));
    memset(vis,false,sizeof(vis));
}
void read(){    //读入数据
    int u,v,w,l,r;
    scanf("%d%d",&n,&m);
    for(int i = 0;i < m; i++){
        scanf("%d%d%d%d%d",&u,&v,&w,&l,&r);
        add(u,v,w,l,r);
        add(v,u,w,l,r);
    }
}
void init_data(int kk){ //初始化数据
    vis[kk] = false;
    dis[kk] = maxx;
}
int solve(int s){
    priority_queue<NODE>q;  //储存最短距离
    q.push(NODE(s,0));  //读入原点
    while(!q.empty()){  //队列为空则无法到达
        int kk = q.top().u; //储存当前最短距离下标
        int minD = q.top().dis; //储存当前最短距离
        q.pop();
        if(kk==n)   //若下标为目标值，return
            return minD;
        vis[kk] = true; //该点是否访问
        for(int l = head[kk]; l!=-1; l=edge[l].next){   //松弛边
            if(!vis[edge[l].to]&&minD<=edge[l].r&&minD>=edge[l].l&&minD + edge[l].w < dis[edge[l].to]){
                dis[edge[l].to] = minD + edge[l].w;
                q.push(NODE(edge[l].to,dis[edge[l].to]));   //将松弛后的边压入队列
            }
        }
        init_data(kk);  //初始化数据
    }
    return 0;
}
int main(){
    scanf("%d",&t);
    while(t--){
        init(); //初始化
        read(); //读入
        printf("%d\n",solve(1));    //解决方案
    }
    return 0;
}

问题 C: 千年老二

时间限制: 1 Sec 内存限制: 128 MB
提交: 24 解决: 12
[提交][状态][讨论版][命题人:qianyouyou]

题目描述

雷婷与万钧是青梅竹马，无论是考试还是玩游戏，雷婷总是第一，而万钧总是第二，尽管万钧有做第一的实力，但他每次都会把第一让给雷婷，仅因为每次读榜单时雷霆万钧听起来是那么顺耳。这天，雷婷参加了 acm 选拔，万钧也跟着雷婷参加。题目是这样的：

有 n 个节点，编号为 1~n，有 m 条边，每条边都有一个距离。两点之间最多只有 1 条边。现在你需要选取 n-1 条边，使得所有点都连接起来都有通路。n-1 条边距离之和越小分数越高。

万钧立马意识到这道题是求最小生成树的，并且每个人的答案不能相同，万钧根据瞪眼法立马瞪出了答案，然而他还是等待雷婷先做完。现在雷婷已经找到了距离最短的1种方案，不过他俩太心有灵犀了，答案一模一样，万钧想获得第 2 名，请你帮万钧想一种方案，距离之和越短越好，但不能和雷婷的结果相同。一条边不同即可认为不同。如果找不到输出 -1。当然存在一种情况，如果雷婷的方案是没有方案求出最短距离，即表示该图没有最小生成树，即输出 -1。总之雷婷的方案是最优解的一种。

输入

存在多组数据，第一行一个正整数 t，表示有 t 组数据。

每组数据第一行有两个整数 n 和 m（2 ≤ n ≤ 100，1 ≤ m ≤ 1000)，之后 m 行，每行三个正整数 s，e，w，表示 s 到 e 的双向路的权值为 w。

输出

输出次小生成树的值（如果存在多个最小生成树或仅有一个树，则次小生成树就是最小生成树，输出-1），如果不存在输出 -1。

样例输入

样例输出

tag：图论、次小生成树

//次小生成树
#include<bits/stdc++.h>
using namespace std;
const int L=1e5+7;
const int inf=0x3f3f3f3f;
const int maxn=1000+7;
int father[maxn],n,m,num[maxn],nPos;    //父节点（并查集），点数，边数，最小生成树点集，当前访问方位
struct node{
    int s,y,w;
}edge[L];   //边集，左端点，右端点，权值
void init(){    //初始化并查集
    for(int i=0;i<=n;i++)
        father[i]=i;
}
int root(int x){    //并查集，构造父节点
    return father[x]==x?x:father[x]=root(father[x]);
}
void unite(int x,int y){    //并查集，合并两个联通图
    x=root(x);
    y=root(y);
    if(x!=y)
        father[y]=x;
}
int alike(int x,int y){ //并查集，判断是否为同一连通图
    return root(x)==root(y);
}
int cmp(node a,node b){ //sort结构体排序
    return a.w<b.w;
}
int secondTree(int pos) //次小生成树
{
    init(); //初始化
    int sum=0,cnt=0;
    for(int i=0;i<m;i++)    //对于删去边后的图进行最小生成树运算
    {
        if(cnt==n-1)
            break;
        if(i==pos)
            continue;
        if(!alike(edge[i].s,edge[i].y)){
            unite(edge[i].s,edge[i].y);
            sum+=edge[i].w;
            cnt++;
        }
    }
    return cnt!=n-1?-1:sum; //判断删除边后是否能构成最小生成树
}
int kruskal(){  //最小生成树
    init();
    sort(edge,edge+m,cmp);  //对边进行权值排序
    int sum=0,cnt=0;
    for(int i=0;i<m;i++)    //每次选择最小且未访问过的一条边
    {
        if(cnt==n-1)
            break;
        if(!alike(edge[i].s,edge[i].y)){
            unite(edge[i].s,edge[i].y);
            sum+=edge[i].w;
            cnt++;
            num[++nPos]=i;
        }
    }
    return cnt!=n-1?-1:sum; //判断边是否大于等于n-1，否则输出-1
}
void read(){    //读入数据
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
        scanf("%d%d%d",&edge[i].s,&edge[i].y,&edge[i].w);
}
void solve(){   //解决方案
    int Min=inf;
    nPos=0;
    int mst=kruskal();  //最小生成树值
    if(mst==-1) {   //没有最小生成树即输出-1
        printf("-1\n");
        return;
    }
    for(int i=1;i<=nPos;i++){   //对最小生成树的每条边进行遍历，选择删边后的最小值
        int secmst=secondTree(num[i]);
        if(secmst!=-1)  //若没有次小生成树输出-1
            Min=min(Min,secmst);
        }
    if(Min!=inf&&Min!=mst)
        printf("%d\n",Min); //输出结果
    else
        printf("-1\n");
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        read(); //读入数据
        solve();    //解决方案
    }
    return 0;
}

问题 F: 给力台球厅

时间限制: 1 Sec 内存限制: 128 MB
提交: 10 解决: 3
[提交][状态][讨论版][命题人:qianyouyou]

题目描述

教练爱打台球。这天偶遇一家台球厅，便进去看看。然而这家台球厅貌似和平常的台球厅不太一样，它的每张桌面上的洞都是随机分布在桌面上的，球也是随机摆放的。

教练立即意识到，此台球厅的桌面不符合正态分布之概率密度函数，而是呈离散分布，顿时患有强迫症的教练心里就不舒服了。为了平缓一下翻腾的内心，教练随机选取了一张球和洞数量一样的球桌，望着奇怪的桌面与奇怪的球，教练脑袋上不禁长出了大把大把的草：如果能求出所有球入洞的最短距离之和该有多好啊。

现有一个桌面面积为 n×m 的台球桌，将台球桌分成 n×m 个小格，台球桌上有许多的洞和许多的球，均匀分布在小格里，且每个小格只有三种状态，有球，有洞，空白。球用 @ 表示，洞用 # 表示，空白的地方用 * 表示。每个洞只能容纳一个球，球每次只能按照上下左右的方向移动，且每移动一格视为移动 1 个单位长度。当一个球被另一个球挡住时，它可以跳球，所以每一个球都可以完全无视其他球或洞的存在而继续前行，直到进自己心仪的洞。现求所有球进洞的距离之和最小是多少。如果你能帮教练解决这道题，恭喜你就是 ACM 队员了（每个球只能进一个洞，每个洞内有球的话就变成空白状态）

输入

多组测试样例，首行输入 m，n，即矩形台球桌面的边长。(2 ≤ m，n ≤ 20，球最多100个，洞最多100个，保证洞和球数量相等)

输出

输出一个整数，即所有球入洞的距离最短是多少。

样例输入

2 2
*#
@*
7 8
****#***
****#***
****#***
@@@@#@@@
****#***
****#***
****#***

样例输出

1
2

2
28

tag：图论、最小费用最大流

//网络流
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f; //无穷大
const int maxn = 60007;
const int maxm = 1000007;
int vis[maxn],d[maxn],pre[maxn],a[maxn],m,n;    //是否访问，最短路，前置节点，流量，边集，点集
char mp[107][107];  //台球地图
struct Edge{
    int u, v, c, cost, next;
}edge[maxm];    //网络流边集

int s[maxn], cnt;   //每个点流量

void init(){    //初始化
	cnt = 0;
	memset(s, -1, sizeof(s));
}

void add(int u, int v, int c, int cost){    //对两点之间进行单向边建立
	edge[cnt].u = u;
	edge[cnt].v = v;
	edge[cnt].cost = cost;
	edge[cnt].c = c;
	edge[cnt].next = s[u];
	s[u] = cnt++;   //建立单向边
	edge[cnt].u = v;
	edge[cnt].v = u;
	edge[cnt].cost = -cost;
	edge[cnt].c = 0;
	edge[cnt].next = s[v];
	s[v] = cnt++;   //建立双向边
}

bool spfa(int ss, int ee,int &flow,int &cost){  //以距离为费用寻找最短路，以最短路为当前增广路
	queue<int> q;
	memset(d, INF, sizeof d);
	memset(vis, 0, sizeof vis); //初始化
	d[ss] = 0, vis[ss] = 1, pre[ss] = 0, a[ss] = INF;
	q.push(ss);
	while (!q.empty()){ //spfa以费用为距离寻找最短路
		int u = q.front();q.pop();
		vis[u] = 0;
		for (int i = s[u]; ~i; i = edge[i].next){   //和当前点相连所有边松弛过程
			int v = edge[i].v;
			if (edge[i].c>0&& d[v]>d[u] + edge[i].cost){    //松弛过程
				d[v] = d[u] + edge[i].cost;
				pre[v] = i;
				a[v] = min(a[u], edge[i].c);    //取最小值
				if (!vis[v]){
					vis[v] = 1;
					q.push(v);     //压入待松弛队列
				}
			}
		}
	}
	if (d[ee] == INF) return 0; //判断是否有最短路，无说明最大流完成
	flow += a[ee];
	cost += d[ee]*a[ee];
	int u = ee;
	while (u != ss){    //求当前最短路下的流量和
		edge[pre[u]].c -= a[ee];
		edge[pre[u] ^ 1].c += a[ee];
		u = edge[pre[u]].u;
	}
	return 1;
}

int MCMF(int ss, int ee){   //最小费用最大流
	int cost = 0, flow=0;   //初始化
	while (spfa(ss, ee, flow, cost));   //寻找增广路径，直到没有增广路径为止
	return cost;    //返回最大流费用
}

struct point{
    int x,y;    //球坐标，洞坐标
};

void solve(){
    point H[107],P[107];    //建立球集与洞集
    int h=0,p=0;
    for(int i=0;i<n;i++){   //输入地图
        scanf("%s",&mp[i]);
        for(int j=0;j<m;j++){
            if(mp[i][j]=='#'){  //若为洞则坐标加入洞集
                H[h].x=i;
                H[h].y=j;
                h++;
            }
            else if(mp[i][j]=='@'){ //若为球则坐标加入球集
                P[p].x=i;
                P[p].y=j;
                p++;
            }
        }
    }
    init(); //初始化
    for(int i=0;i<h;i++)
        for(int j=0;j<p;j++){
        int c=fabs(H[i].x-P[j].x)+fabs(H[i].y-P[j].y);
             add(i+1,h+j+1,1,c);
        }   //建立球与洞之间的路径
    for(int i=0;i<h;i++)    //建立超级源点
        add(0,i+1,1,0);
    for(int i=0;i<p;i++)    //建立超级汇点
        add(h+1+i,h+p+1,1,0);
    printf("%d\n",MCMF(0,h+p+1));   //最小费用最大流
}

int main(){
    while(~scanf("%d%d",&n,&m)){
        if(!(m||n))
            break;
        solve();    //解决方案
    }
	return 0;
}