Poj 1201(差分制約システム)
これは私の5番目の「差分制約システム」です.お祝いに値するのは、本題は完全に自分で作ったもので、何の資料も参考にしていません.ほほほ.....ワクワク・・・
1行目にnを入力し、次にn個の制限条件を入力し、条件のフォーマットはai bi ci、0<=ai<=bi<=50000,1<=ci<=bi-ai+1である.線分[ai,bi]に少なくともci個の点を選択し、選択された点の個数を最小限にし、すべての制限条件を満たし、この最小値を出力することを表す.
テーマ分析:
1.最初は整数(1,2,...)ごとに図のノードとして、追加エッジがadd(b,a,-c)であり、書き出した後、問題のサンプルデータまでエラー結果8を出力ことが分かった.
2.研究したところ、これはだめだということが分かった.例えば、2つの制限条件はそれぞれ:1 3 2、3 6 2;では、上記の考え方に従って、この2つのエッジ<3,1>=-2,<6,3>=-2を追加します.後にまた辺<6,1>=-4を得ることができて、線分[1,6]の上で少なくとも4つの点を選ぶことを意味して、実際にはそうではありませんて、少なくとも3つの点を選ぶべきで、問題はどれですか?線分[1,3]と[3,6]に共通点があるからである.
3.だから、別の方法で図を構築するには、1つの条件(ai,bi,ci)に対して実際には開区間(ai-0.5,bi+0.5)で少なくともci個の整数点を選択することを示しているが、3.5,4.5,5.5...このような小数点は図の結点としましょう.もう1つは、左閉右開区間[ai,bi+1]で、整数点をとるので、意味は閉区間[ai,bi]と同様であり、これにより、各制限条件(ai,bi,ci)に対してエッジ
4.タイトルを追加する制限条件だけでは不十分で、タイトルは線分ごとに少なくとも選択する点数しか与えられていないが、線分[a,b]に対してもう一つ隠れた最大選択点数はb-a+1個であるためadd(a,b+1,b-a+1)とする.
5.図の連通性を保証するために、隣接する2つの整数点i,i+1の辺、区間[i,i+1]に少なくとも0個、最大1個を追加しなければならないので、add(i+1,i,0);add(i,i+1,1)である.
6.大功告成,サンプルデータ正确,提出....悲劇....TLE....
7.poj 3159と同じように、各add(a,b,c)をadd(b,a,c)に変更することで、何倍も時間を節約でき、変更してから提出することができるのか.悲劇......それともTLE
8.やっといくつかの辺が余分であることを発見して、第4点の中のadd(a,b+1,b-a+1)は余分で、後ろにadd(i,i+1,1)があるため、add(a,b+1,b-a+1)を取り除いて、更に提出します.....Accept.....
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXV 50005
#define MAXE 200100
#define INF 100000000
struct
{
int e, v;
} edge[MAXE];
int minV, maxV;
int neg;
int dis[MAXV];
int node[MAXV], next[MAXE];
int Q[MAXV], vst[MAXV];
void add(int s, int e, int v)
{
edge[neg].e = e;
edge[neg].v = v;
next[neg] = node[s];
node[s] = neg++;
}
int relax(int s, int e, int v)
{
if (dis[s]+v < dis[e])
{
dis[e] = dis[s]+v;
return 1;
}
return 0;
}
int SPFA(int s0)
{
int i, t, p, top;
for (i=minV; i<=maxV; i++)
dis[i] = INF;
dis[s0] = 0;
Q[0] = s0;
top = 1;
vst[s0] = 1;
while (top)
{
t = Q[--top];
vst[t] = 0;
p = node[t];
while (p != -1)
{
if (relax(t, edge[p].e, edge[p].v) && !vst[edge[p].e])
{
Q[top++] = edge[p].e;
vst[edge[p].e] = 1;
}
p = next[p];
}
}
return 1;
}
int main()
{
int n, a, b, c, i;
memset(node, -1, sizeof(node));
minV = 50000;
maxV = 0;
scanf("%d", &n);
while (n--)
{
scanf("%d %d %d", &a, &b, &c);
add(b+1, a, -c);
//add(a, b+1, b-a+1); // ， TLE
if (minV > a) minV = a;
if (maxV < b+1) maxV = b+1;
}
for (i=minV; i<maxV; i++)
{
add(i+1, i, 0);
add(i, i+1, 1);
}
SPFA(maxV);
printf("%d/n", -dis[minV]);
}