你先看看是不是卡住了^\_^
by SofanHe @ 2017-11-03 11:41:17
@[多功能的荀彧](/space/show?uid=43931) 我就是找不到啊- -
by youken @ 2017-11-04 08:18:31
# head 数组是局部变量,无法调用
by SofanHe @ 2017-11-04 09:59:26
@[多功能的荀彧](/space/show?uid=43931) 没有啊，我head都是开在前面的啊- -
by youken @ 2017-11-04 23:22:54
head1,head2,head?
by SofanHe @ 2017-11-05 00:06:21
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define REG register
const int maxn=1e5+6;
inline char getc()
{
static char buf[1<<14],*p1=buf,*p2=buf;
return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
int w=1,lwd=0;
char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0'&&ch<='9') lwd=lwd*10+ch-48,ch=getchar();
return lwd*w;
}
return (x%10+10)%10;
}
struct Edge{
int v,next;
}s[maxn*5];
struct New{
int v,next;
}t[maxn*5];
int val[maxn],head[maxn],p=0;
int vis[maxn],color[maxn],dfn[maxn],low[maxn],ss[maxn],top=0,cnt=0,indexx=0;
int topsort[maxn],tot=0;
int x[maxn],y[maxn];
inline void add(REG int u,REG int v)
{
s[++p]=(Edge){v,head[u]};
head[u]=p;
return;
}
inline void addd(REG int u,REG int v)
{
t[++p]=(Edge){v,head[u]};
head[u]=p;
return;
}
inline void tarjan(REG int u)
{
vis[u]=1;
ss[++top]=u;
dfn[u]=low[u]=++indexx;
for(REG int i=head[u];i;i=s[i].next)
{
int to=s[i].to;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v])
low[u]=min(low[u],dfn[u]);
}
if(dfn[u]==low[u])
{
cnt++;
vis[u]=0;
while(ss[top+1]!=u)
{
color[ss[top]]=cnt;
vis[ss[top]]=0;
top--;
}
}
return;
}
int main()
{
int n,m,x,y,z;
n=read(),m=read();
for(REG int i=1;i<=n;i++)
val[i]=read();
for(REG int i=1;i<=m;i++)
{
x[i]=read(),y[i]=read(),z=read();
add(x[i],y[i]);
if(z>1) add(y[i],x[i]);
}
memset(vis,0,sizeof(vis));
memset(head,0,sizeof(head));
for(REG int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
for(REG int i=1;i<=n;i++)
if(!color[i]) color[i]=++cnt;
memset(vis,0,sizeof(vis));
memset(head,0,sizeof(head));
p=0;
for(REG int i=1;i<=n;i++)
{
}
return 0;
}
```
by Explorer_CYC @ 2018-05-07 21:54:14
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define REG register
#define max(a,b) a>b?a:b
#define min(a,b) a>b?b:a
#define E() putchar(10)
using namespace std;
const int maxn=1e6+3;
const int inf=0x3f3f3fll;
typedef long long ll;
inline char getc()
{
static char buf[1<<14],*p1=buf,*p2=buf;
return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
int data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getc();
if(ch=='-') w=-1,ch=getc();
while(ch>='0'&&ch<='9') data=data*10+ch-'0',ch=getc();
return data*w;
}
bool vis[maxn];
queue<int> q;
int x[maxn],y[maxn],type[maxn],n,m,into[maxn];
int val[maxn],topp[maxn],cnt=0,head[maxn],p=0,front[maxn],py=0;
int color[maxn],tot=0,dfn[maxn],low[maxn],indexx=0;
int str[maxn],top=0;
struct Edge{
int v,next;
}s[maxn<<1];
struct EE{
int to,last;
}t[maxn<<1];
inline void add1(REG int u,REG int v)
{
s[++p]=(Edge){v,head[u]};
head[u]=p;
return;
}
inline void add2(REG int u,REG int v)
{
t[++py]=(EE){v,front[u]};
front[u]=py;
return;
}
inline void Tarjan(REG int u)
{
str[++top]=u;
vis[u]=1;
low[u]=dfn[u]=++indexx;
for(REG int i=head[u];i;i=s[i].next)
{
int to=s[i].v;
if(!dfn[u])
{
Tarjan(to);
low[u]=min(low[u],low[to]);
}
else if(vis[to]) low[u]=min(low[u],dfn[to]);
}
if(dfn[u]==low[u])
{
tot++;
vis[u]=0;
while(str[top+1]!=u)//
{
vis[str[top]]=0;
color[str[top]]=tot;
top--;
}
}
return;
}
inline void topsort()
{
for(REG int i=1;i<=tot;i++)
if(!into[i]) q.push(i),topp[++cnt]=i;
while(!q.empty())
{
int x=q.front();
q.pop();
for(REG int i=front[x];i;i=t[i].last)
{
int to=t[i].to;
into[to]--;
if(!into[to]) q.push(to),topp[++cnt]=to;
}
}
return;
}
int main()
{
n=read(),m=read();
for(REG int i=1;i<=n;i++)
val[i]=read();
for(REG int i=1;i<=m;i++)
{
x[i]=read(),y[i]=read(),type[i]=read();
add1(x[i],y[i]);
if(type[i]>1) add1(y[i],x[i]);
}
for(REG int i=1;i<=n;i++)
if(!dfn[i]) Tarjan(i);
for(REG int i=1;i<=m;i++)
{
int a=color[x[i]],b=color[y[i]];
if(a!=b) add2(a,b),into[b]++;
}
topsort();
for(REG int i=1;i<=cnt;i++)
printf("%d ",topp[i]);
return 0;
}
```
by Explorer_CYC @ 2018-05-11 20:14:04
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define REG register
#define max(a,b) a>b?a:b
#define min(a,b) a>b?b:a
#define E() putchar(10)
using namespace std;
const int maxn=1e6+3;
const int inf=0x3f3f3fll;
typedef long long ll;
inline char getc()
{
static char buf[1<<14],*p1=buf,*p2=buf;
return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
int data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getc();
if(ch=='-') w=-1,ch=getc();
while(ch>='0'&&ch<='9') data=data*10+ch-'0',ch=getc();
return data*w;
}
bool vis[maxn];
queue<int> q;
int x[maxn],y[maxn],type[maxn],n,m,into[maxn];
int val[maxn],topp[maxn],cnt=0,head[maxn],p=0,front[maxn],py=0;
int color[maxn],tot=0,dfn[maxn],low[maxn],indexx=0;
int str[maxn],top=0,dp[maxn];
int minn[maxn],maxx[maxn],mx[maxn],mn[maxn];
struct Edge{
int v,next;
}s[maxn<<1];
struct EE{
int to,last;
}t[maxn<<1];
inline void add1(REG int u,REG int v)
{
s[++p]=(Edge){v,head[u]};
head[u]=p;
return;
}
inline void add2(REG int u,REG int v)
{
t[++py]=(EE){v,front[u]};
front[u]=py;
return;
}
inline void Tarjan(REG int u)
{
str[++top]=u;
vis[u]=1;
low[u]=dfn[u]=++indexx;
for(REG int i=head[u];i;i=s[i].next)
{
int to=s[i].v;
if(!dfn[to])
{
Tarjan(to);
low[u]=min(low[u],low[to]);
}
else if(vis[to]) low[u]=min(low[u],dfn[to]);
}
if(dfn[u]==low[u])
{
tot++;
vis[u]=0;
while(str[top+1]!=u)//
{
vis[str[top]]=0;
color[str[top]]=tot;
top--;
}
}
return;
}
inline void topsort()
{
for(REG int i=1;i<=tot;i++)
if(!into[i]) q.push(i),topp[++cnt]=i;
while(!q.empty())
{
int x=q.front();
q.pop();
for(REG int i=front[x];i;i=t[i].last)
{
int to=t[i].to;
into[to]--;
if(!into[to]) q.push(to),topp[++cnt]=to;
}
}
return;
}
int main()
{
n=read(),m=read();
for(REG int i=1;i<=n;i++)
val[i]=read();
for(REG int i=1;i<=m;i++)
{
x[i]=read(),y[i]=read(),type[i]=read();
add1(x[i],y[i]);
if(type[i]>1) add1(y[i],x[i]);
}
for(REG int i=1;i<=n;i++)
if(!dfn[i]) Tarjan(i);
for(REG int i=1;i<=n;i++)
{
for(REG int j=front[i];j;j=t[j].last)
{
int to=t[j].to;
if(i!=to) add2(color[i],color[to]);
into[color[to]]++;
}
}
// for(REG int i=1;i<=py;i++)
// printf("%d %d\n",t[i].to,t[i].last);
// E();
topsort();
// for(REG int i=1;i<=cnt;i++)
// printf("%d ",topp[i]);
memset(minn,0x3f,sizeof(minn));
minn[topp[1]]=mn[topp[1]];
for(REG int i=1;i<=cnt;i++)
{
int x=topp[i];
for(REG int j=front[x];j;j=t[j].last)
{
int to=t[j].to;
minn[to]=min(minn[to],min(minn[x],mn[x]));
dp[to]=max(dp[to],max(dp[x],max(maxx[to],mx[to]-minn[to])));
}
}
printf("%d\n",dp[color[n]]);
return 0;
}
```
by Explorer_CYC @ 2018-05-14 21:13:07