学步园

题目大意：一个图上，每一条边有两个属性ｄ和ｃ，ｄ是允许的最大带宽，ｃ是修建这条边的费用。从顶点０出发，能够到达所有的边。要求在总费用不超过Ｗ的情况下最大带宽是多少。

思路：二分最大带宽，然后求最小树形图，更新最大带宽即可。

#define maxn 10100
#define maxm 10110
struct pp
{
    int u,v;
    int w;
}edge[maxm];
int pre[maxn],id[maxn];
int in[maxn];
int vis[maxn];
int minroot;
int cntt;
void add(int u,int v,int w)
{
    edge[cntt].u=u;
    edge[cntt].v=v;
    edge[cntt].w=w;
    cntt++;
}
int Mst_s(int root,int n,int m)
{
    int ans=0;
    while(true){
        for(int i=0;i<n;i++)
            in[i]=INT_MAX;
        for(int i=0;i<m;i++){
            int u=edge[i].u;
            int v=edge[i].v;
            if(edge[i].w<in[v]&&u!=v){
                pre[v]=u;
                if(u==root)minroot=i;
                in[v]=edge[i].w;
            }
        }
        for(int i=0;i<n;i++){
            if(i==root)continue;
            if(in[i]==INT_MAX)return -1;
        }
        in[root]=0;
        int cnt=0;
        memset(id,-1,sizeof(id));
        memset(vis,-1,sizeof(vis));
        for(int i=0;i<n;i++){
            ans+=in[i];
            int v=i;
            while(vis[v]!=i&&id[v]==-1&&v!=root)vis[v]=i,v=pre[v];
            if(v!=root&&id[v]==-1){
                for(int u=pre[v];u!=v;u=pre[u])id[u]=cnt;
                id[v]=cnt++;
            }
        }
        if(cnt==0)break;
        for(int i=0;i<n;i++)
            if(id[i]==-1)id[i]=cnt++;
        for(int i=0;i<m;i++){
            int v=edge[i].v;
            edge[i].u=id[edge[i].u];
            edge[i].v=id[edge[i].v];
            if(edge[i].u!=edge[i].v)edge[i].w-=in[v];
        }
        n=cnt;
        root=id[root];
    }
    return ans;
}
void ini(){
    cntt=0;
    memset(edge,0,sizeof(edge));
}
struct ppt{
    int u,v,b,c;
}pt[maxn];
int n,m,c;
bool judge(int mid){
    ini();
    int cnt=0;
    for(int i=0;i<m;i++){
        if(pt[i].b>=mid){
        add(pt[i].u,pt[i].v,pt[i].c);cnt++;
        }
    }
    int ans=Mst_s(0,n,cnt);
    if(ans==-1)return false;
    if(ans>c)return false;
    return true;
}
int main(){
    int T;
    scanf("%d",&T);
    for(int tt=1;tt<=T;tt++){
        ini();
        int l=0,r=0;

        scanf("%d%d%d",&n,&m,&c);
        for(int i=0;i<m;i++){
            scanf("%d%d%d%d",&pt[i].u,&pt[i].v,&pt[i].b,&pt[i].c);
            r=max(r,pt[i].b);
        }
        printf("Case %d: ",tt);
        if(!judge(0)){
            puts("impossible");
            continue;
        }
        int mid,ans;
        while(l<=r){
            mid=(l+r)>>1;
            if(judge(mid))l=mid+1,ans=mid;
            else r=mid-1;
        }
        printf("%d kbps\n",ans);
    }
    return 0;
}