标签存档：图论

【题目链接】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;
}

【题目大意】
有一个数组d[1..n]
d[1]=0，d[i]然后给出一些限制，
第一种：x,y,w，d[y]-d[x]<=w（数据保证x第二种：x,y,w，d[y]-d[x]>=w（数据保证x一个d[i]=k满足条件当且仅当存在一组d[1..n]满足限制，而且d[i]=k。
【算法分析】
完全没想到。。。一开始写了个二分+差分判可行了。。。完全超时到天荒地老。。。
后来看正解。
非常Orz。就是按题目的这些不等式建图。
第一次，按最短路来建图，d[1]设为0，然后其他全设为无穷大。跑一遍最短路的spfa。
第二次，按最长路来建图，d[1]设为0，然后其他也全设为0。跑一遍最长路的spfa。

然后、然后、很Orz地他就解决了。。。

最短路跑出的是最大值。
最长路跑出的是最小值。

为什么呢？
因为他都是按照那个不等式最贴边的方式解得。
所以最短路就是刚好<=那个上界。
而最长路则是刚好>=那个下界。

So，Orz。。。。
【CODE】
#include #include #include #include #include using namespace std;
const int N=5005;
const int INF=100000000;
int n;
int L[N],R[N],d[N],Q[N],v[N],Inn[N];
bool flag;
struct edge{int x,y,w;edge *next;};
struct Link_t{
edge sp[N],*ls[N];
int e;
void init(){
e=0;
for (int i=1;i<=n;i++) ls[i]=NULL;
}

void addedge(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];
}
}Hate,Love,G;

void input(){
int ml,mh,i,x,y,w;
scanf("%d%d%d",&n,&ml,&mh);
Hate.init();
Love.init();
for (i=1;i<=ml;i++){
scanf("%d%d%d",&x,&y,&w);
Love.addedge(x,y,w);
}
for (i=1;i<=mh;i++){
scanf("%d%d%d",&x,&y,&w);
Hate.addedge(x,y,w);
}
}

void build1(){
G.init();
int i;
for (i=1;i<=Love.e;i++){
edge *t=&Love.sp[i];
G.addedge(t->x,t->y,t->w);
}
for (i=1;i<=Hate.e;i++){
edge *t=&Hate.sp[i];
G.addedge(t->y,t->x,-t->w);
}
for (i=1;i G.addedge(i+1,i,-1);
G.addedge(1,n,INF);
}

void spfa1(){
for (int i=1;i<=n;i++){
Inn[i]=0;
v[i]=0;
d[i]=INF+22;
}
int head=0,tail=1;
d[1]=0; Q[1]=1; v[1]=1;
while (head!=tail){
head++; if (head>=N) head=0;
for (edge *t=G.ls[Q[head]];t;t=t->next)
if (d[t->x]+t->w d[t->y]=d[t->x]+t->w;
if (d[t->y]<0){
flag=false;
return;
}
if (!v[t->y]){
v[t->y]=1;
tail++; if (tail>=N) tail=0;
Q[tail]=t->y;
Inn[t->y]++;
if (Inn[t->y]>n){
flag=false;
return;
}
}
}
v[Q[head]]=0;
}
}

void build2(){
G.init();
int i;
for (i=1;i<=Love.e;i++){
edge *t=&Love.sp[i];
G.addedge(t->y,t->x,-t->w);
}
for (i=1;i<=Hate.e;i++){
edge *t=&Hate.sp[i];
G.addedge(t->x,t->y,t->w);
}
for (i=1;i G.addedge(i,i+1,1);
G.addedge(n,1,-INF);
}

void spfa2(){
for (int i=1;i<=n;i++){
v[i]=0;
d[i]=0;
}
int head=0,tail=1;
d[1]=0; Q[1]=1; v[1]=1;
while (head!=tail){
head++; if (head>=N) head=0;
for (edge *t=G.ls[Q[head]];t;t=t->next)
if (d[t->x]+t->w>d[t->y]){
d[t->y]=d[t->x]+t->w;
if (!v[t->y]){
v[t->y]=1;
tail++; if (tail>=N) tail=0;
Q[tail]=t->y;
}
}
v[Q[head]]=0;
}
}

void output(){
puts("Exist!");
for (int i=1;i<=n;i++)
printf("%d %dn",L[i],R[i]);
}

int main(){
int Tc;
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
printf("Case #%d: ",i);
input();
flag=true;
build1();
spfa1();
if (!flag){
puts("Not Exist!");
continue;
}
for (int j=1;j<=n;j++) R[j]=d[j];
build2();
spfa2();
for (int j=1;j<=n;j++) L[j]=d[j];
output();
}
}

【题外话】
这题之前写过一个题解了。
地址是：http://hi.baidu.com/edwardmj/blog/item/592566ad221c3ac07cd92a87.html
之前的算法没有AC。然后看了到处转了一转，又围观了神牛的代码。
各种构造法弄到头晕。。。
Orz。。。还是没看懂。然后我写起了当时扬言要写的随机算法。
【算法分析】
同样是当作树来DFS。
DFS时就判断当前点有没有1这种颜色。没有的话染1。
再判断有没有2这种颜色。没有的话染2。
否则得话，染颜色rand()%2+1。
然后出来以后还没染得，就看两边缺啥就染啥。
如果无解的话，重新染。直到无解10次那就真无解。
否则输出。
【评测结果】
Test # Score Time Memory Result 1 6.5 0.00s 6652 kB Correct! 2 6.5 0.00s 6652 kB Correct! 3 6.5 0.00s 6652 kB Correct! 4 6.5 0.00s 6652 kB Correct! 5 52.0 0.00s 6652 kB Correct! 0.00s 6652 kB Correct! 0.00s 6652 kB Correct! 0.00s 6652 kB Correct! 0.00s 6652 kB Correct! 0.01s 6652 kB Correct! 0.00s 6652 kB Correct! 0.00s 6652 kB Correct! 6 52.0 0.50s 9696 kB Correct! 0.09s 6652 kB Correct! 0.00s 6652 kB Correct! 0.13s 9696 kB Correct! 0.12s 7608 kB Correct! 0.19s 8288 kB Correct! 0.11s 7416 kB Correct! 0.12s 7944 kB Correct! 【CODE】
#include #include #include const int N=105555;
struct edge{int x,y,c,next,op;}g[N*2];
int n,e,times=0;
int ls[N],du[N],c1[N],c2[N];
bool v[N];

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

void init(){
e=0;
memset(ls,0,sizeof(ls));
memset(du,0,sizeof(du));
int i,x,y,m;
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++){
scanf("%d%d",&x,&y);
addedge(x,y);
du[x]++; du[y]++;
}
}

void draw(int t,int co){
g[t].c=co; g[g[t].op].c=co;
if (co==1){c1[g[t].x]++; c1[g[t].y]++;}
else{c2[g[t].x]++; c2[g[t].y]++;}
}

void dfs(int p){
for (int t=ls[p];t;t=g[t].next)
if (!v[g[t].y]){
v[g[t].y]=true;
if (!c1[p]) draw(t,1);
else if (!c2[p]) draw(t,2);
else draw(t,rand()%2+1);
dfs(g[t].y);
}
}

void work(){
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
memset(v,false,sizeof(v));
for (int i=1;i<=e;i++) g[i].c=0;
for (int i=1;i<=n;i++)
if (!v[i]){
v[i]=true;
dfs(i);
}
for (int t=1;t<=e;t++)
if (!g[t].c)
if (!c1[g[t].x] && du[g[t].x]>1 || !c1[g[t].y] && du[g[t].y]>1) draw(t,1);
else draw(t,2);
bool flag=true;
for (int i=1;i<=n;i++)
if (du[i]>1 && (!c1[i] || !c2[i])) flag=false;
if (!flag){
if (times<10){
times++;
work();
return;
}
printf("0n");
}
else
for (int i=1;i printf("%dn",g[i].c);
}

int main(){
srand(19930505);
// freopen("input2.txt","r",stdin);
// freopen("output.txt","w",stdout);
init();
work();
}

【题目地址】http://evaluator.hsin.hr/login.php?redirect=index.php
【题目大意】
一个N,E<=10^5的无向图
每条边可以染黑白两色。
求一个染色方案，使每一个度>1的点，都拥有与之相连的黑边和白边。
【算法分析】
。。。我只会骗分了，应该还可以写个随机调整搞一下。
我是把它当树来走，树边染上dep[p] mod 2+1的颜色。
然后其他边如果只有某一边需要，那么就完成那一边的需求。
否则随便完成某一边的需求。
【数据通过情况】
Test # Score Time Memory Result 1 0.0 0.00s 6956 kB You program printed 0, but there is a valid solution. 2 6.5 0.00s 6956 kB Correct! 3 6.5 0.00s 6956 kB Correct! 4 0.0 0.00s 6956 kB You program printed 0, but there is a valid solution. 5 0.0 0.00s 6956 kB Correct! 0.00s 6956 kB You program printed 0, but there is a valid solution. 0.00s 6956 kB You program printed 0, but there is a valid solution. 0.00s 6956 kB Correct! 0.00s 6956 kB You program printed 0, but there is a valid solution. 0.00s 6956 kB You program printed 0, but there is a valid solution. 0.00s 6956 kB Correct! 0.00s 6956 kB Correct! 6 0.0 0.11s 10000 kB Correct! 0.09s 6956 kB Correct! 0.00s 6956 kB You program printed 0, but there is a valid solution. 0.11s 10000 kB You program printed 0, but there is a valid solution. 0.10s 7916 kB You program printed 0, but there is a valid solution. 0.11s 8592 kB You program printed 0, but there is a valid solution. 0.11s 7720 kB Correct! 0.10s 8248 kB You program printed 0, but there is a valid solution.
显然。。。因为它搞到多组测试数据，完全没办法得很多分。。。但是过的点也不少了。。。
求正解
【CODE】
#include #include #include const int N=105555;
struct edge{int x,y,color,next,op;}g[N*2];
int n,e;
int ls[N],dep[N],du[N],donec[N],fa[N];

inline void addedge(int x,int y){
g[++e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e; g[e].op=e+1;
g[++e].x=y; g[e].y=x; g[e].next=ls[y]; ls[y]=e; g[e].op=e-1;
}

void init(){
int i,x,y,m;
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++){
scanf("%d%d",&x,&y);
addedge(x,y);
du[x]++; du[y]++;
}
}

inline void draw(int t,int co){
if (g[t].color) return;
if (co==3 || co==1){
g[t].color=1;
g[g[t].op].color=1;
}
else{
g[t].color=2;
g[g[t].op].color=2;
}
if (!donec[g[t].x]) donec[g[t].x]=co;
if (donec[g[t].x]!=co) donec[g[t].x]=3;
if (!donec[g[t].y]) donec[g[t].y]=co;
if (donec[g[t].y]!=co) donec[g[t].y]=3;
}

void dfs(int p){
for (int t=ls[p];t;t=g[t].next)
if (!dep[g[t].y]){
dep[g[t].y]=dep[p]+1;
fa[g[t].y]=t;
draw(t,dep[p]%2+1);
dfs(g[t].y);
}
else if (g[t].op!=fa[p]){
if (donec[g[t].y]==3) draw(t,3-donec[p]);
else if (donec[g[t].y]==donec[p]) draw(t,3-donec[p]);
else draw(t,donec[p]);
}
}

void work(){
int i;
for (i=1;i<=n;i++)
if (!dep[i]){
dep[i]=1;
dfs(i);
}
}

void update(int p){
donec[p]=0;
for (int t=ls[p];t;t=g[t].next){
if (!donec[p]) donec[p]=g[t].color;
if (donec[p]!=g[t].color) {donec[p]=3; return;}
}
}

bool Try_opc(int ss){
for (int t=ls[g[ss].x];t;t=g[t].next)
if (g[t].color==g[ss].color && t!=ss){
g[ss].color=3-g[ss].color;
g[g[ss].op].color=g[ss].color;
donec[g[ss].x]=3;
update(g[ss].y);
return true;
}
return false;
}

void solve(){
bool flag=true;
for (int i=1;i<=n;i++)
for (int t=ls[i];t && du[i]>1 && donec[i]!=3;t=g[t].next)
if (Try_opc(t)) break;
for (int i=1;i<=n;i++)
if (du[i]>1 && donec[i]!=3){
flag=false;
}
if (!flag){
printf("0n");
return;
}
for (int i=1;i printf("%dn",g[i].color);
}

int main(){
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
init();
work();
solve();
}