6 November in 614

Contest

A. greet

map，完了。

B. gift

map，完了。

C. [Usaco2008 Nov Gold] 安慰奶牛

最小生成树。新边权设为原边权的两倍，再加上两端点的点权。完了……

前三题真是增添我的自信心！（一遍过！当然前三题我都写过原题了……真实水平体现不出来。）

D. [NOIP2009TG] 最优贸易

SPFA 双向广搜。（还没搞明白，之后再更）

贴一发 90 分卡时限代码（说不定再乱搞一下就满分了……）：

#include <cstdio>

int n, m, p[100005];

int head[100005], nex[1000006], to[1000006];

int dp[100005], v[100005];

inline int read() {

    int res=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar();

    while (ch>='0'&&ch<='9') res=res*10+ch-'0', ch=getchar();

    return res;

}

inline int min(int x, int y) {return x>y?y:x; }

inline int max(int x, int y) {return x>y?x:y; }

inline void add(int x, int y) {

    nex[++head[0]]=head[x], head[x]=head[0], to[head[0]]=y;

}

void dfs(int x, int fa, int mi) {

    int flag=1;

    mi=min(mi, p[x]); if (v[x]!=mi) v[x]=mi, flag=0;

    int s=max(dp[fa], p[x]-mi); if (dp[x]<s) dp[x]=s, flag=0;

    if (flag) return;

    for (register int i=head[x]; i; i=nex[i]) dfs(to[i], x, mi);

}

int main() {

    n=read(), m=read();

    for (register int i=1; i<=n; ++i) p[i]=read();

    for (register int i=1, x, y, z; i<=m; ++i) {

        scanf("%d%d%d", &x, &y, &z);

        add(x, y); if (z>1) add(y, x);

    }

    dfs(1, 0, 0x3f3f3f3f);

    printf("%d\n", dp[n]);

    return 0;

}

巴特西

6 November in 614

Contest

A. greet

B. gift

C. [Usaco2008 Nov Gold] 安慰奶牛

D. [NOIP2009TG] 最优贸易

最新文章

热门文章