【题意】
你需要花费不超过cost元来搭建一个比赛网络。网络中有n台机器，编号0~n-1，其中机器0为服务器，其他机器为客户机。一共有m条可以使用的网线，其中第i条网线的发送端是机器ui，接收端是机器vi（数据只能从机器ui单向传输到机器vi），带宽是bi Kbps,费用是ci元。每台客户机应当恰好从一台机器接收数据。你的任务是最大化网络中的最小带宽。
Input
First line of input contains T (≤ 50), the number of test cases. This is followed by T test cases.
Each test case starts with an integer N, M, C (1 ≤ N ≤ 60, 1 ≤ M ≤ 10^4, 1 ≤ C ≤ 10^9), the
number of universities and the number of possible links, and the budget for setting up the network.
Each university is identified by an integer between 0 and N − 1, where 0 is the server.
Next M lines each contain 4 integers, u, v, b, c (0 ≤ u, v < N, 1 ≤ b, c ≤ 10^6, u ̸= v), describing
a possible link from university u to university v, that has the bandwidth of b kbps and of cost c. All
links are unidirectional.
There is a blank line before each test case.
Output
For each test case, output the maximum bandwidth to stream.
If it’s not possible, output ‘streaming not possible.’.
Sample Input
3
3 4 300
0 1 128 100
1 2 256 200
2 1 256 200
0 2 512 300
3 4 500
0 1 128 100
1 2 256 200
2 1 256 200
0 2 512 300
3 4 100
0 1 128 100
1 2 256 200
2 1 256 200
0 2 512 300
Sample Output
128 kbps
256 kbps
streaming not possible.
【分析】
一开始看错题了ORZ,直接无视有向图，直接二分+MST。。
好吧看过来之后就是多了个方向而已。。
那就是MDST，要用朱-刘算法，，中国人发明的吧？？
hhhh
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 110
#define Maxm 10010
#define INF 0xfffffff int n,m,mc; struct node
{
int x,y,b,c;
};
node t[Maxm],tt[Maxm]; bool cmp(node x,node y) {return x.c<y.c;}
int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;} int fa[Maxn]; int ffa(int x)
{
if(fa[x]!=x) fa[x]=ffa(fa[x]);
return fa[x];
} int in[Maxn],pre[Maxn],id[Maxn],vis[Maxn];
//in -> 最小入边 边权
//pre -> 最小入边的发出点
//id -> 所在圈的编号
//vis 所在链顶端 int rt; bool check(int mid) //MDST
{
rt=;
int ans=;
int nn=n;
for(int i=;i<=m;i++) tt[i]=t[i];
while()
{
//1、找最小入边
for(int i=;i<=nn;i++) in[i]=INF;
for(int i=;i<=m;i++)
{
int x=tt[i].x,y=tt[i].y;
if(tt[i].c<in[y]&&x!=y&&tt[i].b>=mid) //因为缩边，所以可能有自环
{
pre[y]=x;
in[y]=tt[i].c;
}
}
//2、判断是否有最小生成树
for(int i=;i<=nn;i++) if(i!=rt)
{
if(in[i]==INF) return ;
}
//3、找环
int cnt=;
memset(id,-,sizeof(id));
memset(vis,-,sizeof(vis));
in[rt]=;
for(int i=;i<=nn;i++)
{
ans+=in[i];
int now=i;
while(vis[now]!=i&&id[now]==-&&now!=rt)
{
vis[now]=i;
now=pre[now];
}
if(now!=rt&&id[now]==-)
{
cnt++;
for(int j=pre[now];j!=now;j=pre[j])
{
id[j]=cnt;
}
id[now]=cnt;
}
}
if(cnt==) break;//没有圈啦233
for(int i=;i<=nn;i++) if(id[i]==-)
id[i]=++cnt; //相当于自己一个圈
//4、缩点，重新标记
for(int i=;i<=m;i++)
{
int x=tt[i].x,y=tt[i].y;
tt[i].x=id[x];tt[i].y=id[y];
if(tt[i].x!=tt[i].y)
{
tt[i].c-=in[y];
}
}
nn=cnt;
rt=id[rt];
}
return ans<=mc;
} void ffind(int l,int r)
{
int ans=-;
while(l<=r)
{
int mid=(l+r)>>;
if(check(mid)) ans=mid,l=mid+;
else r=mid-;
}
if(ans==-) printf("streaming not possible.\n");
else printf("%d kbps\n",ans);
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&mc);
int mn=INF,mx=;
for(int i=;i<=m;i++)
{
scanf("%d%d%d%d",&t[i].x,&t[i].y,&t[i].b,&t[i].c);
t[i].x++;t[i].y++;
mn=mymin(mn,t[i].b);
mx=mymax(mx,t[i].b);
}
sort(t+,t++m,cmp);
ffind(mn,mx);
}
return ;
}
// vis相当于一个不清0的bool
2016-11-01 10:43:31
记录一下MDST做法，求有向最小生成树，也叫最小树形图。
主过程：
1、给所有非根节点选一条权最小的入边。
2、如果有一个点没有入边，那么无解。
3、判断选出来的点是否构成圈，给每个点打上他所在的圈的编号标记（一定是i一个简单环，因为每个点只选一条入边）
4、缩点，求出新的图。
注意：
第4步，入边的权值不是单纯的原图权值，还要减去圈里面和他矛盾的边的权值。
时间复杂度：O（VE）
如果一开始没有给你根怎么破???????????
如果是不定根的情况我们可以虚拟一个根，让虚拟根到每个节点的距离为图上所有边的权值之和加一。这样找到最小树形图后再减掉所有边的权值之和加一就可以了。
搜刮网上MDST的解释：
图论是ACM竞赛中比较重要的组成部分，其模型广泛存在于现实生活之中。因其表述形象生动，思维方式抽象而不离具体，因此深受各类喜欢使劲YY的Acmer的喜爱。这篇文章引述图论中有关有向图最小生成树的部分，具体介绍朱刘算法的求解思路，并结合一系列coding技巧，实现最小树型图O（VE）的算法，并在最后提供了该算法的模版，以供参考。
关于最小生成树的概念，想必已然家喻户晓。给定一个连通图，要求得到一个包含所有顶点的树（原图的子图），使之所构成的边权值之和最小。在无向图中，由于边的无向性质，所以求解变得十分容易，使用经典的kruskal与prim算法已经足够解决这类问题。而在有向图中，则定义要稍微加上一点约束，即以根为起点，沿给定有向边，可以访问到所有的点，并使所构成的边权值之和最小，于是问题开始变得不一样了，我们称之为最小树型图问题。
该问题是由朱永津与刘振宏在上个世纪60年代解决的，值得一提的是，这2个人现在仍然健在，更另人敬佩的是，朱永津几乎可以说是一位盲人。解决最小树型图的算法后来被称作朱刘算法，也是当之无愧的。
首先我们来阐述下算法的流程：算法一开始先判断从固定根开始是否可达所有原图中的点，若不可，则一定不存在最小树形图。这一步是一个很随便的搜索，写多搓都行，不加废话。第二步，遍历所有的边，从中找出除根结点外各点的最小入边，累加权值，构成新图。接着判断该图是否存在环。若不存在，则该图便是所求最小树型图，当前权为最小权。否则对环缩点，然后回到第二步继续判断。
这里存在一系列细节上的实现问题，以确保能够达到VE的复杂度。首先是查环，对于新图来说只有n-1条入边，对于各条入边，其指向的顶点是唯一的，于是我们可以在边表中添加from，表示该边的出发点，并考虑到如果存在环，则对环上所有边反向，环是显然同构的，于是最多作V次dfs就能在新图中找到所有的环，并能在递归返回时对顶点重标号进行缩点，此步的重标号可以用hash数组映射。然后就是重要的改边法，对于所有不在环上的边，修改其权为w-min(v)，w为当前边权，min(v)为当前连接v点的最小边权。其数学意义在于选择当前边的同时便放弃了原来的最小入边。我们可以知道，每次迭代选边操作O(E)，缩点操作O(V)，更新权操作O(E)，至少使一个顶点归入生成树，于是能在V-1步内完成计算，其复杂度为O(VE)。
以上为定根最小树型图，对于无固定根最小树型图，只要虚拟一个根连所有的点的权为边权总和+1，最后的结果减去(边权+1)即可。另外对于求所定的根标号，只要搜索被选中的虚边就可以判断了。
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring> using namespace std; const int N=,M=,inf=;
struct edge {int u,v,w;} e[M];
int n,m,ans,id[N],pre[N],v[N],inw[N]; void zhu_liu(int root)
{
int s,t,idx=n;
while (idx)
{
for (int i=;i<=n;++i) inw[i]=inf,id[i]=-,v[i]=-;
for (int i=;i<=m;++i)
{
s=e[i].u;t=e[i].v;
if (e[i].w>inw[t] || s==t) continue;
pre[t]=s;
inw[t]=e[i].w;
}
inw[root]=;pre[root]=root;
for (int i=;i<=n;++i)
{
if (inw[i]==inf)
{
printf("impossible\n");
return;
}
ans+=inw[i];
}
idx=;
for (int i=;i<=n;++i)
if (v[i]==-)
{
t=i;
while (v[t]==-) v[t]=i,t=pre[t];
if (v[t]!=i || t==root) continue;
id[t]=++idx;
for (s=pre[t];s!=t;s=pre[s]) id[s]=idx;
}
if (idx==) continue;
for (int i=;i<=n;++i)
if (id[i]==-) id[i]=++idx;
for (int i=;i<=m;++i)
{
e[i].w-=inw[e[i].v];
e[i].u=id[e[i].u];
e[i].v=id[e[i].v];
}
n=idx;
root=id[root];
}
printf("%d\n",ans);
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=m;++i)
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
zhu_liu();
return ;
}