状压DP

CodeForces 11D A Simple Task

Posted on

今天做的不太一样的状压,从去年的专题找的,看到学长并没有写是已经写过了么?
可能是因为跟图论相关的原因吧。

题意:
给你一个简单图,让你找出简单环的数量。
附 : 简单环就是没有重边和重点的环。
点数为 19 。

思路:
19个点,一般很容易想到状压和二维……根据数据猜算法?
事实上我是没有想到二维的

dp[ s ] [ p ] 表示 s 集合 p 为当前位置的边数 ,初始对每个状态 dp [ 1<< i ][ i ] 设置为 1
对于每一个状态,固定的从最小的一位 1 作为起点,从这个起点开始扩散,如果能回到这个起点,就进行计数。

因为对于一个环,枚举起点和终点的话,会存在起点到终点,和以终点为起点的情况。
比如说 1-> 2 -> 3 ->1 和 3 -> 2 -> 1 -> 3

AC Code

#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 20;
typedef long long ll;

int map[maxn][maxn], n, m, u, v;
ll dp[1 << maxn][maxn];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        u--, v--;
        map[u][v] = map[v][u] = 1;
    }
    ll ans = 0;
    for (int i = 0; i < maxn; i++)
        dp[1 << i][i] = 1;
    for (int st = 1; st < (1 << n); st++) {
        int s = __builtin_ctz(st); //右边第一个1的位置
        for (int e = s; e < n; e++) {  //枚举集合元素 作为当前位置
            if (st & (1 << e)) {
                for (int i = s; i < n; i++) {  // 扩散状态
                    int nst = st | (1 << i);
                    if (map[e][i] && (st & (1 << i)) == 0) { //新状态
                        dp[nst][i] += dp[st][e];
                        if (map[i][s] && __builtin_popcount(nst) > 2) // 能回到起点 1的数量也就是边数大于2
                            ans += dp[st][e]; 
                    }
                }
            }
        }
    }
    printf("%lld\n", ans / 2);
    return 0;
}

状压DP

CodeForces 8 C Looking for Order

Posted on

前几天刚写了一道状压DP入门题,结果这次就遇到了,在比赛最后一点时间一眼看破,无奈只有想法,写不来……

不过赛后尝试写的时候遇到了一个自己不会的问题,也就是说假如比赛的时候开了这道题,我也会一直卡着。

题意:
给你很多个行李的位置和起点的位置,要你把所有行李搬运到起点,一次只能搬一个或者两个,花费是距离,求最小花费。行李最多24个。

思路
状压dp,对于每一个状态,我们通过dp维护其最优。
因为这里的拿取行李是与顺序无关的,那么,我通过从小到大枚举状态,在保证我当前状态最优的前提下,由我当前状态拓展而来的状态只要通过比较就可以达到最优好暴力
所以我通过枚举,找到第一个它能够搬运的行李,每次都拓展这个状态即可。

AC Code

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
const int max_n = 30;
const int max_m = 1 << 24;

int n, tmp;
int dp[max_m], pre[max_m];

pii nodes[max_n];
int dis[max_n][max_n];

inline int calcul(int a, int b)
{
    return (nodes[a].first - nodes[b].first) * (nodes[a].first - nodes[b].first) + (nodes[a].second - nodes[b].second) * (nodes[a].second - nodes[b].second);
}

int main()
{
    scanf("%d %d %d", &nodes[29].first, &nodes[29].second, &n);
    nodes[n] = nodes[29];
    each(i, n) scanf("%d %d", &nodes[i].first, &nodes[i].second);
    each(i, n + 1) range(j, i + 1, n) dis[i][j] = dis[j][i] = calcul(i, j);
    fill(dp, 0x3f), dp[0] = 0;
    each(i, (1 << n)) if (dp[i] != inf) each(j, n) if (!(i & (1 << j)))
    {
        int t = (i | (1 << j));
        if (dp[t] > (tmp = dp[i] + 2 * dis[j][n])) {
            dp[t] = tmp;
            pre[t] = i;
        }
        each(k, n) if (!(t & (1 << k)))
        {
            int p = (t | (1 << k));
            if (dp[p] > (tmp = dp[i] + dis[k][n] + dis[j][n] + dis[k][j])) {
                dp[p] = tmp;
                pre[p] = i;
            }
        }
        break ;
    }
    int cur = (1 << n) - 1, ps, det;
    printf("%d\n0 ", dp[cur]);
    while (cur != 0) {
        ps = pre[cur];
        det = cur - ps;
        each(i, n) if (det & (1 << i)) printf("%d ", i + 1);
        printf("0 ");
        cur = ps;
    }
    return 0;
}
2-SAT

URAL 1382 Game with Cards

Posted on

Table of contents

题解

2-SAT 一眼题,但是很遗憾,我之前刷的专题里面没有输出可行解的题。我不知道怎么输出可行解,我个人以为,只要染色数量等于点数就是可行解。有哪里不对的么??

但我至少认可了Yasola巨巨在挑程上说的拓扑排序输出可行解的说法。

传送门

题意
有n个人手中有n张卡,每个人说两句话,有一句必定为真,有一句必定为假。说了2-sat一眼题……
两句话分别说,我自己手上是几号卡,别人手上是几号卡,保证不存在相同的陈述。

思路:
对于每两个人 i 和 j 的陈述,进行判断,如果产生矛盾,则建边。

产生矛盾是指两个的陈述,主语或者谓语有一个不同就产生了矛盾。
eg
1 号 手中有 2 号卡 < ---- > 1 号手中有 3 号卡
1 号 手中有 2 号卡 < ---- > 2 号手中有 2 号卡

两人的陈述分别是

陈述12
ai -> a[i]b[i] -> c[i]
bj -> a[j]b[j] -> c[j]

建边方式如下 a 表示 a 的 1 语句是对的 ,~a 表示 a 的 2 语句是对的

矛盾建边a1a2
b1a -> ~b , b -> ~a~a -> ~ b , b -> a
b2a -> b , ~b -> ~a~a -> b , ~b -> a

根据Yasola巨巨所说,求2-sat应该有三个常用算法

  1. 暴力法
  2. Tarjan
  3. Kosaraju

第三种算法昨天才知道,现在还没学,先贴上 1 和 2 的AC Code

暴力法

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int maxn = 2005;

int idx, n, m, vis_time, top;
int head[maxn], st[maxn];
bool instack[maxn], vis[maxn];
int a[maxn], b[maxn], c[maxn], num[maxn];

struct node {
    int to;
    int nxt;
} edges[1005 * 1005 * 2];

void addEdge(int u, int v)
{
    edges[idx].to = v;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

void init()
{
    for (int i = 0; i < 2 * n; i++)
        head[i] = -1;
}

void CreateGraph()
{
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] == a[j]) {
                addEdge(i << 1, j << 1 | 1);
                addEdge(j << 1, i << 1 | 1);
            }
            if (b[i] == b[j] || c[i] == c[j]) {
                addEdge(i << 1 | 1, j << 1);
                addEdge(j << 1 | 1, i << 1);
            }
            if (i + 1 == b[j] || a[i] == c[j]) {
                addEdge(i << 1, j << 1);
                addEdge(j << 1 | 1, i << 1 | 1);
            }
            if (b[i] == j + 1 || c[i] == a[j]) {
                addEdge(i << 1 | 1, j << 1 | 1);
                addEdge(j << 1, i << 1);
            }
        }
    }
}

bool dfs(int u)
{
    if (vis[u ^ 1])
        return false;
    if (vis[u])
        return true;
    vis[u] = true;
    st[top++] = u;
    for (int id = head[u]; ~id; id = edges[id].nxt)
        if (!dfs(edges[id].to))
            return false;
    return true;
}

bool solve()
{
    for (int i = 0; i < 2 * n; i += 2) {
        if (!vis[i] && !vis[i + 1]) {
            top = 0;
            if (!dfs(i)) {
                while (top)
                    vis[st[--top]] = false;
                if (!dfs(i + 1))
                    return false;
            }
        }
    }
    return true;
}

int main()
{
    scanf("%d", &n);
    init();
    for (int i = 0; i < n; i++)
        scanf("%d %d %d", a + i, b + i, c + i);
    CreateGraph();
    if (solve())
        for (int i = 0; i < n; i++)
            printf("%d ", vis[i << 1] ? 1 : 2);
    return 0;
}

Tarjan

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int maxn = 2005;

int idx, tpidx, n, m, scc, top, vis_time;
int head[maxn], tphead[maxn], dfn[maxn], low[maxn], in[maxn], color[maxn], st[maxn];
bool instack[maxn], vis[maxn], judge[maxn];
int a[maxn], b[maxn], c[maxn], indegree[maxn];
int crs[maxn], col[maxn];

queue<int> que;

struct node {
    int from, to;
    int next;
} edges[1005 * 1005 * 2], tp_edges[1005 * 1005 * 2];

void addEdge(int u, int v)
{
    edges[idx].from = u;
    edges[idx].to = v;
    edges[idx].next = head[u];
    head[u] = idx++;
}

void addTPEdge(int u, int v)
{
    tp_edges[tpidx].from = u;
    tp_edges[tpidx].to = v;
    tp_edges[tpidx].next = tphead[u];
    tphead[u] = tpidx++;
}

void tarjan(int u)
{
    int v;
    low[u] = dfn[u] = vis_time++;
    instack[u] = true;
    st[++top] = u;
    for (int id = head[u]; ~id; id = edges[id].next) {
        v = edges[id].to;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (instack[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        scc++;
        do {
            v = st[top--];
            instack[v] = false;
            color[v] = scc;
        } while (v != u);
    }
}

void CreateGraph()
{
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] == a[j]) {
                addEdge(i << 1, j << 1 | 1);
                addEdge(j << 1, i << 1 | 1);
            }
            if (b[i] == b[j] || c[i] == c[j]) {
                addEdge(i << 1 | 1, j << 1);
                addEdge(j << 1 | 1, i << 1);
            }
            if (i + 1 == b[j] || a[i] == c[j]) {
                addEdge(i << 1, j << 1);
                addEdge(j << 1 | 1, i << 1 | 1);
            }
            if (b[i] == j + 1 || c[i] == a[j]) {
                addEdge(i << 1 | 1, j << 1 | 1);
                addEdge(j << 1, i << 1);
            }
        }
    }
}

void topoSort()
{
    for (int i = 1; i <= scc; i++)
        if (indegree[i] == 0)
            que.push(i);
    while (!que.empty()) {
        int cur = que.front();
        que.pop();
        if (col[cur] == 0) {
            col[cur] = 1;
            col[crs[cur]] = -1;
        }
        for (int id = tphead[cur]; ~id; id = tp_edges[id].next)
            if (--indegree[tp_edges[id].to] == 0)
                que.push(tp_edges[id].to);
    }
}

bool getAns()
{
    for (int i = 0; i < n; i++) {
        if (color[i << 1] == color[i << 1 | 1])
            return false;
        crs[color[i << 1]] = color[i << 1 | 1];
        crs[color[i << 1 | 1]] = color[i << 1];
    }
    for (int i = 0; i < idx; i++) { 
        if (color[edges[i].from] != color[edges[i].to]) {
            addTPEdge(color[edges[i].to], color[edges[i].from]);
            indegree[color[edges[i].from]]++;
        }
    }
    topoSort();
    for (int i = 0; i < n; i++)
        judge[i] = col[color[i << 1]] == 1 ? true : false;
    return true;
}

void init()
{
    while (!que.empty())
        que.pop();
    for (int i = 0; i < 2 * n; i++)
        tphead[i] = head[i] = -1;
}

int main()
{
    scanf("%d", &n);
    init();
    for (int i = 0; i < n; i++)
        scanf("%d %d %d", a + i, b + i, c + i);
    CreateGraph();
    for (int i = 0; i < 2 * n; i++)
        if (dfn[i] == 0)
            tarjan(i);
    if (getAns())
        for (int i = 0; i < n; i++)
            printf("%d ", judge[i] ? 1 : 2);
    return 0;
}
简单DP

POJ 1661 Help Jimmy

Posted on

好题!!!!
这道题我整整想了一个晚上,怎么说呢,应该还是我从一开始就没想复杂,考虑得简单了,然后后面就写的很复杂了……

其实我在写到一半的时候就突然想到我的状态转移方程是错的,然而还是抱着poj数据弱的侥幸继续写下去……然后错误的地方越写越清晰……

题意:
一个90后都玩过的空间游戏吧,记得叫 是男人就下一百层 ,题意不是很好描述,可以自己去玩玩。

思路:
先说一下我最开始的想法,不想看的直接往下翻。
这道题我一看,诶,水题!我只要每次移动都保证当前层所花时间最少,类似记忆化搜索,一步一步推过去就能保证我的答案最优……

首先这个思路的确是对的,但却忽略了一个细节,从我以前走过的层到我当前层,有个位置上的关系。
就是说当我每次得到当前层时间最短的时候,我必须把落下的相应位置给确定下来,否则,若存在重复的最优时间,当前下落位置不同,会影响之后的时间。这是显然的。
而我要想补救我的思路,那我必须记录所有的位置,虽然这个位置数量不会超过2,但这实现起来就很烦。

正解:
其实正解是很简单的,我只要反向思考就可以了。就是记录当前层到底层的最短时间。考虑当前层到中间层再到底层,则中间层的起始位置必定是当前层的两边。若不存在中间层。则时间为高度,其实这个可以省略

所以只要考略每层的两边是否能到中间层即可。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int inf = 0x3f3f3f3f;

struct node {
    int l, r, h;
    bool operator<(const node& a) const { return h < a.h; }
} s[1005];

int dp[1005][2];
int main()
{
    int n, t, x, y, limit;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d%d", &n, &x, &y, &limit);
        s[0].l = s[0].r = x, s[0].h = y;
        range(i, 1, n) scanf("%d%d%d", &s[i].l, &s[i].r, &s[i].h);
        sort(s, s + n + 1), fill(dp, 0);
        each(i, n + 1)
        {
            bool flag = false;
            reach(j, i) if (s[i].h - s[j].h <= limit && s[i].l >= s[j].l && s[i].l <= s[j].r)
            {
                dp[i][0] = min(dp[j][0] + s[i].l - s[j].l, dp[j][1] + s[j].r - s[i].l);
                flag = true;
                break;
            }
            if (!flag)
                dp[i][0] = s[i].h - s[0].h > limit ? inf : 0;
            flag = false;
            reach(j, i) if (s[i].h - s[j].h <= limit && s[i].r >= s[j].l && s[i].r <= s[j].r)
            {
                dp[i][1] = min(dp[j][0] + s[i].r - s[j].l, dp[j][1] + s[j].r - s[i].r);
                flag = true;
                break;
            }
            if (!flag)
                dp[i][1] = s[i].h - s[0].h > limit ? inf : 0;
        }
        printf("%d\n", min(dp[n][0], dp[n][1]) + y);
    }
    return 0;
}
思维

HDU 6038 Function

Posted on

多校第一场没有怎么想的题,然而实际上是很简单的……就是题意在理解上有点绕。

题意:
给你两个序列a和b,每个序列中的每个元素各不相同,且分别为 [0,num)
要你求满足如下函数的数量。\( f ( i ) = b_{ f(a_i) } \)

思路:
一般人一眼就可以看出是一个递归的函数过程。
每次当我们知道了 \( f(i) \) ,我们就可以很顺利地得出 \( f(a_i) \) ,知道了 \( f(a_i) \) ,我们就可以很顺利的知道 \( f( a_{a_i} ) \)

又因为序列的特性,则对于这个函数,在a序列上必定会存在一个环。
而相应的,在a序列上的一个环与b序列上的元素相对应起来,只有在b序列上存在a序列环的因子才能成立。这个真的只要随便意淫一下就可以了,你要我证明我想还真有点烦

因此只要求出两个序列的环,对于每一对a序列的环与b序列的环,如果b序列环是a序列环的因子,则加上b序列环长度,因为对于a序列上的一个固定点,每一个b序列环上的点都可以对应与a序列固定点,且对应关系必不相同。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;

int a[maxn], b[maxn];
bool vis[maxn];
vector<int> xa, xb;

int dfs(int pos, int ary[], int len)
{
    if (vis[pos])
        return len;
    vis[pos] = true;
    return dfs(ary[pos], ary, len + 1);
}

int main()
{
    int n, m, cas = 0;
    while (scanf("%d%d", &n, &m) != EOF) {
        each(i, n) scanf("%d", a + i);
        each(i, m) scanf("%d", b + i);
        fill(vis, false), xa.clear(), xb.clear();
        each(i, n) if (!vis[i]) xa.push_back(dfs(i, a, 0));
        fill(vis, false);
        each(i, m) if (!vis[i]) xb.push_back(dfs(i, b, 0));
        int sa = xa.size(), sb = xb.size();
        ll ans = 1;
        each(i, sa)
        {
            ll tmp = 0;
            each(j, sb) if (xa[i] % xb[j] == 0)(tmp += xb[j]) %= mod;
            ans = (ans * tmp) % mod;
        }
        printf("Case #%d: %lld\n", ++cas, ans);
    }
    return 0;
}
贪心

HDU 6034 Balala Power!

Posted on

多校第一场的恶心题……因为前几天补题数量太多,博客一直没写,现在补上……

这道题我整整写了一个下午+晚上,mmp,一方面是题目本身恶心,另一方面也反映了我的脑子问题。

题意:
给你指定数量的小写字符串,让你把字母,转化成数字,也就是说 a-z 各自对应 0-25。要求所得数字和最大。
同时转化出的数字不能出现前导零。

思路:
将每个字符的贡献转化成一个25进制的数,用一个 26× 1e5 的数组存储,将其进行排升序。
再是考虑前导零的情况,反向遍历找到第一个不存在前导零的数字标记一下即可。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;

int n, len, max_len;
char buf[maxn];
ll mul[maxn];
bool lead[30];
int a[30];

struct ch {
    int num[maxn];
    int pos;
    void init(int id)
    {
        pos = id;
        memset(num, 0, sizeof num);
    }
    bool operator<(const ch& a) const
    {
        for (int i = max_len - 1; i >= 0; i--) {
            if (num[i] != a.num[i])
                return num[i] < a.num[i];
        }
        return false;
    }
} key[27];

int change(char sen[])
{
    int len = strlen(sen);
    for (int i = 0; i < len / 2; ++i) {
        char ch = sen[i];
        sen[i] = sen[len - i - 1];
        sen[len - i - 1] = ch;
    }
    return len;
}

int main()
{
    mul[0] = 1;
    for (int i = 1; i < maxn; i++)
        mul[i] = mul[i - 1] * 26 % mod;
    int cas = 0;
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < 26; i++)
            key[i].init(i), lead[i] = false;
        max_len = 0;
        while (n--) {
            scanf("%s", buf);
            len = change(buf);
            if (len > 1)
                lead[buf[len-1] - 'a'] = true;
            max_len = max(max_len, len);
            for (int i = 0; i < len; ++i)
                key[buf[i] - 'a'].num[i]++;
        }
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < max_len; ++j) {
                key[i].num[j + 1] += key[i].num[j] / 26;
                key[i].num[j] %= 26;
            }
            while (key[i].num[max_len] > 0) {
                key[i].num[max_len + 1] += key[i].num[max_len] / 26;
                key[i].num[max_len++] %= 26;
            }
        }
        sort(key, key + 26);
        int zero = -1;
        for (int i = 0; i < 26; ++i)
            if (!lead[key[i].pos]) {
                zero = key[i].pos;
                break;
            }
        ll res = 0, x = 25;
        for (int i = 25; i >= 0; --i) {
            if (key[i].pos != zero) {
                for (int j = 0; j < maxn; j++)
                    res = (res + x * key[i].num[j] * mul[j] % mod) % mod;
                x--;
            }
        }
        printf("Case #%d: %lld\n", ++cas, res);
    }
    return 0;
}
双联通分量

HDU 6041 I Curse Myself

Posted on

多校第一场的小锅,因为就算给我时间我也写不出来的题……算是小锅吧,还有三个大锅在背上。

开头先说一声,薛昊这个坑比,woc,跟我说这里的k小生成树是就是先取一个最小的,连上每一条边……

然后我在用优先队列的时候我就真的先推小的……
md debug好久才发现……醉了。

题意:
给你一个仙人掌图,要你求出前k小的生成树。将之与k相乘求和 mod 2 ^ 32

思路:
如果是一个一般图,那问题将非常困难,但他是一个仙人掌图,对于一个生成树来说,整张图的桥必定不能删掉,所以必须从每一个环中删掉一条边,而我们删掉的边要求前k大。

将每一个环的边作为集合,多个集合合并,求出前k大,这是一个经典问题。

方法是对每两个集合两两合并,将两个集合的边各自相连,用优先队列推出前k大,但这样时间和空间复杂度都很高。

一个与优先队列思想相似并且简单的方法就是,我们将旧集合维护有序,在这里为降序,并用一个优先队列存储两集合权值和。
首先将新集合的每个元素与旧集合最大元素(就是首位置)相加并加入队列。每次推出一个最大元素的时候,都将这个最大元素在新集合的原元素与旧集合相应元素的下一个元素相加加入队列。
以此推出k个元素存入集合。

这里写的是暴力求解法,tarjan求解接近tle边缘……

这里有个小技巧,就是我们要对结果取 2^ 32 膜 , 值得注意的是 int 存储的总数就是 2 ^ 32 ,而 unsighed int 的范围则刚好是 [ 0 , 2 ^ 32) 所以我们只要用一个int存储,输出 用 %u 就会为我们自动按要求取 膜 。这应该是出题人特意设置的。但的确很妙。

AC Code

#include <cstdio>
#include <cstring>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int max_n = 1010;
const int max_k = 1e5 + 5;
int n, m, k, idx, sum, cnt;
int head[max_n], fa[max_n], dep[max_n], eval[max_n], down[max_n];
int dsu[max_n];

int roll[3][max_k], cur, pre = 1;

struct Edge {
    int to, next, weight;
    Edge() {}
    Edge(int _to, int _next, int _weight) { to = _to, next = _next, weight = _weight; }
} edges[max_n << 1];

struct NonTreeEdge {
    int from, to, weight;
    NonTreeEdge() {}
    NonTreeEdge(int _from, int _to, int _weight) { from = _from, to = _to, weight = _weight; }
} NTedges[max_n];

struct node {
    int val, pos;
    node() {}
    node(int _val, int _pos) { val = _val, pos = _pos; }
    bool operator<(const node& a) const { return val < a.val; }
};

priority_queue<node> que;

int addEdge(int u, int v, int w)
{
    edges[idx] = Edge(v, head[u], w);
    head[u] = idx++;
    edges[idx] = Edge(u, head[v], w);
    head[v] = idx++;
    return 0;
}

int dsuFind(int u) { return dsu[u] < 0 ? u : dsu[u] = dsuFind(dsu[u]); }

bool dsuMerge(int u, int v)
{
    u = dsuFind(u), v = dsuFind(v);
    if (u == v)
        return false;
    dsu[u] = v;
    return true;
}

void dfs(int u)
{
    for (int id = head[u]; ~id; id = edges[id].next) {
        int v = edges[id].to;
        if (v == fa[u])
            continue;
        fa[v] = u;
        dep[v] = dep[u] + 1;
        eval[v] = edges[id].weight;
        dfs(v);
    }
}

inline void read(int& x)
{
    x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
        ch = getchar();
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
}

int main()
{
    int u, v, w, cas = 0;
    while (scanf("%d %d", &n, &m) != EOF) {
        fill(head, -1), fill(dsu, -1), idx = cnt = sum = 0;
        while (m--) {
            read(u), read(v), read(w);
            sum += w;
            dsuMerge(u, v) ? addEdge(u, v, w) : (NTedges[cnt++] = NonTreeEdge(u, v, w), 1);
        }
        dfs(1);
        read(k);
        roll[cur][0] = 1, roll[cur][1] = 0;
        for (int id = 0; id < cnt; id++) {
            int u = NTedges[id].from, v = NTedges[id].to, &sz = roll[2][0] = 1;
            roll[2][1] = NTedges[id].weight;
            while (dep[u] > dep[v])
                roll[2][++sz] = eval[u], u = fa[u];
            while (dep[u] < dep[v])
                roll[2][++sz] = eval[v], v = fa[v];
            while (u != v) {
                roll[2][++sz] = eval[u];
                roll[2][++sz] = eval[v];
                u = fa[u], v = fa[v];
            }
            cur ^= 1, pre ^= 1;
            while (!que.empty())
                que.pop();
            for (int i = 1; i <= sz; i++) {
                down[i] = 1;
                que.push(node(roll[2][i] + roll[pre][1], i));
            }
            for (int& i = roll[cur][0] = 0; i < k && !que.empty();) {
                int val = que.top().val, pos = que.top().pos;
                que.pop();
                roll[cur][++i] = val;
                if (down[pos] < roll[pre][0]) {
                    val = roll[2][pos] + roll[pre][++down[pos]];
                    que.push(node(val, pos));
                }
            }
        }
        int ans = 0;
        for (int i = roll[cur][0], tmp = 0; i > 0; i--) {
            tmp += sum - roll[cur][i];
            ans += tmp;
        }
        printf("Case #%d: %u\n", ++cas, ans);
    }
    return 0;
}