福田做网站公司怎么选择,wordpress怎样在列表页使用瀑布流,php mysql 网站建设,科技公司起名前言 这是评测记录 正题
AC评测记录链接#xff1a; https://www.luogu.org/record/show?rid7945350 大意
一个图#xff0c;没错要求不能走重复的边和点。求走最多次的情况下路最短。 解题思路
每次行走就是一个流量在流#xff0c;然后将边权设为1就可以保证边只能走…前言 这是评测记录 正题
AC评测记录链接 https://www.luogu.org/record/show?rid7945350 大意
一个图没错要求不能走重复的边和点。求走最多次的情况下路最短。 解题思路
每次行走就是一个流量在流然后将边权设为1就可以保证边只能走一次。之后就是点只能走一次将一个点拆为入点和出点连进来的连入点连出去的连出点然后之间连一条边权为1的边这样那个点就只能走一次了。 代码
#includecstdio
#includecstring
#includealgorithm
using namespace std;
struct line{int to,w,c,next;
}a[100081];
int tot,n,m,s,t,f[501],ls[501],tail,answer;
int state[501],x,y,w,c,ans,head,pre[501];
bool v[501];
void addl(int x,int y,int w,int c)
{a[tot].toy;a[tot].ww;a[tot].cc;a[tot].nextls[x];ls[x]tot;a[tot].tox;a[tot].w0;a[tot].c-c;a[tot].nextls[y];ls[y]tot;
}
bool spfa()
{for (int i1;it;i)f[i]2147483647;head0;tail1;v[s]true;state[1]s;f[s]0;while (head!tail){headhead%t1;int xstate[head];for (int qls[x];q;qa[q].next){int ya[q].to;if (a[q].wf[x]a[q].cf[y]){f[y]f[x]a[q].c;pre[y]q;if (!v[y]){v[y]true;tailtail%t1;state[tail]y;}}}v[x]false;}if (f[t]2147483647) return 0;else return 1;
}
void upway()
{int now;ansf[t];nowt;answer1;while (now!s){a[pre[now]].w--;a[pre[now]^1].w;nowa[pre[now]^1].to;}
}
int main()
{tot1;scanf(%d%d,n,m);s1;t2*n;addl(s,2,2147483647,0);addl(t-1,t,2147483647,0);//起点和终点可以走无数遍for (int i2;in;i)addl(i*2-1,i*2,1,0);//连入点和出点for (int i1;im;i){scanf(%d%d%d,x,y,c);addl(x*2,y*2-1,1,c);//连接}while (spfa()) upway();printf(%d %d,answer,ans);
}
