网站置顶jq,wordpress微信分享,推广网站弄哪家好,电子商务网站建设行情前言
9月做的题现在不会了#xff1f;#xff1f;#xff1f; 越学越拉了属于是。
解析
设 disxdis_xdisx 表示 1-x 的最小距离#xff0c;那么一条 u-v 的边的边权就是 disv−disudis_v-dis_udisv−disu。 差分约束即可。
挂掉的坑点#xff1a;只需要考虑…前言
9月做的题现在不会了 越学越拉了属于是。
解析
设 disxdis_xdisx 表示 1-x 的最小距离那么一条 u-v 的边的边权就是 disv−disudis_v-dis_udisv−disu。 差分约束即可。
挂掉的坑点只需要考虑1可以到达的点
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned ll
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)inline ll read() {ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-) f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N2e4100;
const int mod1e97;
const int inf1e9100;
const double eps1e-9;bool mem1;bool Flag0;inline ll ksm(ll x,ll k,int mod){ll res(1);x%mod;while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}int n,m;int dp[N];
vectorinte[N];
int u[N],v[N];
struct node{int to,nxt,w;
}p[N1];
int fi[N],cnt;
inline void addline(int x,int y,int w){p[cnt](node){y,fi[x],w};fi[x]cnt;
}int find(int x){if(dp[x]!-1) return dp[x];if(xn) return dp[x]1;dp[x]0;for(int to:e[x]) dp[x]|find(to);return dp[x];
}
queueintq;
int dis[N],len[N];
bool vis[N];
void spfa(){memset(dis,0x3f,sizeof(dis));dis[1]0;q.push(1);while(!q.empty()){int xq.front();q.pop();vis[x]0;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(!dp[to]) continue;if(dis[to]dis[x]p[i].w){dis[to]dis[x]p[i].w;len[to]len[x]1;if(len[to]n){puts(-1);exit(0);}if(!vis[to]){q.push(to);vis[to]1;}}}}return;
}bool mem2;
signed main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endif//debug(mem%.4lf\n,abs(mem2-mem1)/1024./1024);memset(dp,-1,sizeof(dp));memset(fi,-1,sizeof(fi));cnt-1;nread();mread();for(int i1;im;i){u[i]read();v[i]read();e[u[i]].push_back(v[i]);}find(1);for(int i1;in;i){if(dp[i]-1) dp[i]0;}if(!dp[1]){puts(-1);return 0;}for(int i1;im;i){if(dp[v[i]]0) continue;addline(u[i],v[i],9);addline(v[i],u[i],-1);}spfa();printf(%d %d\n,n,m);for(int i1;im;i){int resdis[v[i]]-dis[u[i]];resmax(res,1);resmin(res,9);printf(%d %d %d\n,u[i],v[i],res);}return 0;
}
/*
*/
