分类存档：默认分类

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1927
【算法分析】
我感觉挺巧妙的。。。想了好一会儿。
首先注意到，每个点最终的入度都为1。
如果把最终停在这个点不再向后走，看成是向汇点连一条边的话，那么每个点的出度都为1。
然后呢？
我们相当于取N条边。这N条有向边除了和源点相连的以外，都是不重头，不重尾的。
这想到了什么？
匹配！
因为头尾可以看成二分图的两边~于是变成最小权匹配。但是由于与源点相连的可以重合，所以新增一个二分图X部的点，利用网络流给它赋予INF这么大的容量。
然后最小费用流完美解决。
【其它】1A。
Orz。。。好不容易又排第一。。。
1 24143 edward_mj 1004K 1917MS G++ 1.90K 2010-05-18 20:41:38 2 23595 nehzilrz 888K 1964MS G++ 1.68K 2010-05-16 13:54:28 3 23547 oimaster 824K 2091MS G++ 2.48K 2010-05-16 11:05:34 4 23681 gaoxin 1256K 2683MS Pascal 1.95K 2010-05-16 18:44:59 5 23196 root 868K 2714MS G++ 1.47K 2010-05-14 14:05:05 6 23813 FDhyc 1436K 2965MS Pascal 3.32K 2010-05-17 13:33:23 【CODE】
#include #include #include const int E=2000000;
const int N=1000005;
const int INF=1000000000;
struct edge{int x,y,c,w;edge *next,*op;}sp[E],*ls[N],*fa[N];
int n,m,S,T,e,cost;
int d[N],v[N],L[N];

void addedge(int x,int y,int c,int w){
e++;
sp[e].x=x; sp[e].y=y; sp[e].c=c; sp[e].w=w;
sp[e].next=ls[x]; ls[x]=&sp[e]; sp[e].op=&sp[e+1];
e++;
sp[e].x=y; sp[e].y=x; sp[e].c=0; sp[e].w=-w;
sp[e].next=ls[y]; ls[y]=&sp[e]; sp[e].op=&sp[e-1];
}

void input(){
scanf("%d%d",&n,&m);
S=n+n+2; T=S+1;
for (int i=1,x;i<=n;i++){
scanf("%d",&x);
addedge(S-1,i+n,1,x);
}
addedge(S,S-1,INF,0);
for (int i=1,x,y,w,tmp;i<=m;i++){
scanf("%d%d%d",&x,&y,&w);
if (x>y) {tmp=x;x=y;y=tmp;}
addedge(x,y+n,1,w);
}
for (int i=1;i<=n;i++){
addedge(S,i,1,0);
addedge(i+n,T,1,0);
}
}

bool spfa(){
int head=0,tail=1;
for (int i=1;i<=T;i++){
d[i]=INF;
v[i]=0;
}
d[S]=0; v[S]=1; L[1]=S;
while (head!=tail){
head++; if (head>=N) head=0;
for (edge *t=ls[L[head]];t;t=t->next)
if (t->c && d[t->x]+t->w d[t->y]=d[t->x]+t->w;
fa[t->y]=t;
if (!v[t->y]){
v[t->y]=1;
tail++; if (tail>=N) tail=0;
L[tail]=t->y;
}
}
v[L[head]]=0;
}
if (d[T]==INF) return false;
return true;
}

void change(){
int nf=INF;
for (int i=T;i!=S;i=fa[i]->x)
if (fa[i]->c nf=fa[i]->c;
cost+=nf*d[T];
for (int i=T;i!=S;i=fa[i]->x){
fa[i]->c-=nf;
fa[i]->op->c+=nf;
}
}

int main(){
input();
cost=0;
while (spfa()) change();
printf("%dn",cost);
}

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1922
【算法分析】
这个显然必须按照”保护图“的拓扑序来搞。
然后我就模拟那个”保护图“拓扑的过程。
不过期间用最小堆来存放结点的d[i]值。
堆中存放的都是入度为0，且尚未扩展的点。
然后每次取堆顶元素拿出来扩展。
扩展方法如下。
1、
首先把”保护图“中的边弄掉。（其实就是拓扑排序的过程）
然后如果出现可新加入的点，那么update一下他，然后把他放入堆。
update(i)的意思是：d[i]=min(max(limit,d[x]+w)) 其中limit为当前点的d值。
x为在”时间图“中有边x->i的点。w就是该边对应的权值了。
2、
在”时间图“里扩展，假如有我能到的点，而且他的入度以为0，那么可以min一下我走过去的时间。

然后最后输出d[n]。
实际上第一种扩展方式是第二种的漏掉的补充，YY一下就能明白。
【时间复杂度】O((n+m) lg n)
【其它】
泪奔。。。好久没排过第一了。时间是最快的。。。当然，其实挺接近。
然后最后一个是我徒弟~
他的方法完全暴力。
k次spfa，每次判整个d数组是否和前一次的不同，然后拓扑扩展一下，将本次在队列里的点的保护去除。
Orz。。。这样的都能过。。。
1 23953 edward_mj 2392K 326MS G++ 3.06K 2010-05-17 22:02:49 2 23587 nehzilrz 12700K 373MS G++ 1.29K 2010-05-16 13:51:06 3 23691 gaoxin 13488K 466MS Pascal 1.18K 2010-05-16 19:11:12 4 23360 oimaster 1060K 513MS G++ 1.56K 2010-05-15 15:50:58 5 23339 jsn1993 1244K 591MS G++ 1.10K 2010-05-15 07:53:14 6 23184 root 45784K 1152MS G++ 1.14K 2010-05-14 13:40:08 7 23188 FDhyc 45784K 1230MS G++ 1.14K 2010-05-14 13:56:02 8 23936 54525871 2064K 2013MS Pascal 2.48K 2010-05-17 21:12:32 【CODE】
#include #include #include #define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
typedef __int64 lld;
const int E=1000005;
const int N=3005;
const int INF=1000000000;
int n,m;
int du[N],zz[N];
lld d[N];

struct edge{int x,y,w;edge *next;};
struct Link_t{
int e;
edge sp[E],*ls[N];
void init(){
e=0;
for (int i=0;i }

void add(int x,int y,int w){
e++;
sp[e].x=x; sp[e].y=y; sp[e].w=w; sp[e].next=ls[x];
ls[x]=&sp[e];
}
}Graph,Protect,Graphop;

struct Heap_t{
int tot,a[N],tmp;

void swap(int x,int y){
tmp=a[x]; a[x]=a[y]; a[y]=tmp;
zz[a[x]]=x; zz[a[y]]=y;
}

void up(int k){
while (k>1 && d[a[k/2]]>d[a[k]]){
swap(k/2,k);
k/=2;
}
}

void down(int k){
int p;
while (k*2<=tot){
p=k*2;
if (p+1<=tot && d[a[p+1]] if (d[a[p]] swap(p,k);
k=p;
}else break;
}
}

void ins(int key){
a[++tot]=key;
zz[key]=tot;
up(tot);
}

void del(){
swap(1,tot);
zz[a[tot]]=0;
tot–;
if (tot<1) return;
down(1);
}

void repair(int p){
up(p);
down(p);
}
}heap;

void input(){
Graph.init();
Protect.init();
Graphop.init();
memset(du,0,sizeof(du));
scanf("%d%d",&n,&m);
for (int i=1,x,y,w;i<=m;i++){
scanf("%d%d%d",&x,&y,&w);
Graph.add(x,y,w);
Graphop.add(y,x,w);
}
for (int i=1,Num,x,j;i<=n;i++){
scanf("%d",&Num);
for (j=1;j<=Num;j++){
scanf("%d",&x);
Protect.add(x,i,0);
du[i]++;
}
}
}

void update(int p,lld limit){
for (edge *t=Graphop.ls[p];t;t=t->next)
if (max(d[t->y]+t->w,limit) d[p]=max(d[t->y]+t->w,limit);
}

void topsort(){
int i;
edge *t;

for (i=1;i<=n;i++) d[i]=(lld)(INF)*INF;
d[1]=0;
heap.tot=0;

for (i=1;i<=n;i++)
if (!du[i]) heap.ins(i);

while (heap.tot>0){
int x=heap.a[1];
heap.del();
for (t=Protect.ls[x];t;t=t->next){
du[t->y]–;
if (!du[t->y]){
update(t->y,d[x]);
heap.ins(t->y);
}
}
for (t=Graph.ls[x];t;t=t->next)
if (!du[t->y] && d[t->y]>d[t->x]+t->w){
d[t->y]=d[t->x]+t->w;
heap.repair(zz[t->y]);
}
}
}

int main(){
input();
topsort();
printf("%I64dn",d[n]);
return 0;
}