3212
地上有一堆卡片。捡起来需要时间，必须一张一张捡起。根据给定关系，如果有特定卡片b，捡起卡片a的时间会加快。
手里已有“THE_WINDY"卡。
连虚根1到所有卡片（除上述），权值为捡起该卡片的原本时间，其他边根据给定关系连接。再连虚根2到虚根1和”THE_WINDY"，边权为已知总权和+1。做最小树形图，将得到的答案减小到sum+1以下（去掉多余的边，至多两条）。
ps当然一个虚根也可以做。
我擦，最后一题最小树形图竟然把模板打错了，wa了半天。
附代码：
/*
Coded by BUPT-[aswmtjdsj] @ Penalty
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <string>
#include <sstream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <ctime>
#include <cstdlib>
#include <map>
#include <set>
#include <cmath>
#include <queue>
#define see(x) cerr << " LINE " << __LINE__ << ":" << #x << " : " << x << endl
#define SP system("pause")
using namespace std;
const double pi = acos(-1.0);
const double eps = 1e-8;
const int inf = ~0u >> 1;
const int dx[4] = {0,0,-1,1};
const int dy[4] = {-1,1,0,0};
#define left(x) ((x) << 1)
#define right(x) (((x) << 1) + 1)
#define parent(x) ((x) >> 1)
#define maxv 1000
#define maxe (maxv * maxv)
#define sqr(x) ((x) * (x))
#define PQ priority_queue
#define PB push_back
int n;
#define maxn 105
#define maxm 400
int cnt,cnt0;
#define type int
struct edge
{
int p,q;
type cost;
edge(){}
edge(int a,int b,type c):p(a),q(b),cost(c){}
}e[maxm];
type in[maxn];
int pre[maxn],vis[maxn],id[maxn];
type dirmst(int root,int nv,int ne)
{
type ans = 0;
while(1)
{
fill(in,in + nv,inf);
for(int i = 0;i < ne;i++)
{
int u = e[i].p;
int v = e[i].q;
if(e[i].cost < in[v] && u != v)
{
pre[v] = u;
in[v] = e[i].cost;
}
}
for(int i = 0;i < nv;i++)
{
if(i == root)
continue;
if(in[i] == inf)
return -1;
}
int cntnode = 0;
fill(id,id + nv,-1);
fill(vis,vis + nv,-1);
in[root] = 0;
for(int i = 0;i < nv;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] = cntnode;
id[v] = cntnode++;
}
}
if(cntnode == 0)
break;
for(int i = 0;i < nv;i++)
if(id[i] == -1)
id[i] = cntnode++;
for(int i = 0;i < ne;i++)
{
int v = e[i].p;
e[i].p = id[e[i].p];
e[i].q = id[e[i].q];
if(e[i].p != e[i].q)
e[i].cost -= in[v];
}
nv = cntnode;
root = id[root];
}
return ans;
}
int main()
{
while(scanf("%d",&n) == 1 && n)
{
int sum = 0;
map<string,int> M;
M["THE_WINDY"] = 1;
cnt = 2;
cnt0 = 0;
for(int i = 1;i <= n;i++)
{
char opt[25];
int num;
scanf("%s %d",opt,&num);
string a(opt);
if(M[a] == 0)
M[a]=cnt++;
e[cnt0++] = edge(0,M[a],num);
sum += num;
scanf("%s %d",opt,&num);
string b(opt);
if(a != b)
{
if(M[b] == 0)
M[b]=cnt++;
e[cnt0++] = edge(M[b],M[a],num);
sum += num;
}
}
for(int i = 0;i <= 1;i++)
e[cnt0++] = edge(cnt,i,sum + 1);
cnt++;
int ans = dirmst(cnt - 1,cnt,cnt0);
while(ans > sum + 1)
ans -= sum + 1;
printf("%d\n",ans);
}
}
2121
同一种思想，两种实现。- -||一种wa的莫名其妙，一种瞬间ac。怨念。
1000个点，10000条边，根未给定，找最小树形图，并输出根。
做法（根据notonlysuccess大神）：加一个虚根，连到已有图中的所有点，边权为原图所有边权之和+1。
做完最小树形图之后的解减去这个值就是最小树形图的解的权和（如果大于这个值的两倍说明无解）。
输出根的时候挺蛋疼。把最初的图记下来，每次找最小入边的时候看看出点是不是虚根，维护一个值记录与虚根连接的点，最后一次被更新的点一定是实根。
附代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
#define maxn 1005
#define maxm 11005
#define type int
const int inf = ~0u >> 1;
struct edge
{
int u,v;
type cost;
int oldu,oldv;
edge(){}
edge(int a,int b,type c,int d,int e):u(a),v(b),cost(c),oldu(d),oldv(e){}
}e[maxm];
int pre[maxn],id[maxn],vis[maxn];
int mark;
type in[maxn];
type dirmst(int root,int nv,int ne)
{
type ret = 0;
int cnt = 0;
int oldroot = root;
while(1)
{
cnt++;
fill(in,in + nv,inf);
for(int i = 0;i < ne;i++)
{
int u = e[i].u;
int v = e[i].v;
if(e[i].cost < in[v] && u != v)
{
if(e[i].oldu == oldroot)
mark = e[i].oldv;
pre[v] = u;
in[v] = e[i].cost;
}
}
for(int i = 0;i <nv;i++)
{
if(i == root)
continue;
if(in[i] == inf)
return -1;
}
int cntnode = 0;
fill(id,id + nv,-1);
fill(vis,vis + nv,-1);
in[root] = 0;
for(int i = 0;i < nv;i++)
{
ret += 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] = cntnode;
id[v] = cntnode++;
}
}
if(cntnode == 0)
break;
for(int i = 0;i < nv;i++)
if(id[i] == -1)
id[i] = cntnode++;
for(int i = 0;i < ne;i++)
{
int v = e[i].v;
e[i].u = id[e[i].u];
e[i].v = id[e[i].v];
if(e[i].u != e[i].v)
e[i].cost -= in[v];
}
nv = cntnode;
root = id[root];
}
return ret;
}
int n,m;
int main()
{
while(scanf("%d %d",&n,&m) == 2)
{
int sum = 0;
mark = -1;
for(int i = 0;i < m;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
e[i] = edge(a,b,c,a,b);
sum += c;
}
int temp = m;
for(int i = 0;i < n;i++)
e[temp++] = edge(n,i,sum + 1,n,i);
int ans = dirmst(n,n + 1,temp);
if(ans > 2 * (sum + 1))
puts("impossible");
else
printf("%d %d\n",ans - sum - 1,mark);
puts("");
}
}
Down