六盘水做网站,网站seo排名优化,怎么做这个购物网站,网站建设哪家比较专业传送门
题意#xff1a; 思路#xff1a; 一开始被题意迷惑了#xff0c;没看出来差分约束#xff0c;老菜鸡啦。首先看到ajai1a_ja_i1ajai1可以把aia_iai分成奇偶#xff0c;让后这个图就变成一个二分图了。再考虑如何连边#xff1a; (1) 对于b1b1b1的情况 思路 一开始被题意迷惑了没看出来差分约束老菜鸡啦。首先看到ajai1a_ja_i1ajai1可以把aia_iai分成奇偶让后这个图就变成一个二分图了。再考虑如何连边 (1) 对于b1b1b1的情况ajai1a_ja_i1ajai1转化成不等式就是aiaj−1a_ia_j-1aiaj−1和ajai1a_ja_i1ajai1所以建图方式为(j,i,−1)(j,i,-1)(j,i,−1)和(i,j,1)(i,j,1)(i,j,1)。 (2) 对于b0b0b0的情况∣ai−aj∣1|a_i-a_j|1∣ai−aj∣1去掉不等式又可以分成两种情况 ①①① ajai1a_ja_i1ajai1 连边方式跟上面一样 ②②② aiaj1a_ia_j1aiaj1转化成不等式aiaj1a_ia_j1aiaj1和ajai−1a_ja_i-1ajai−1连边为(j,i,1)(j,i,1)(j,i,1)和(i,j,−1)(i,j,-1)(i,j,−1)。 可以发现第二种情况有四条边即(i,j,1),(i,j,−1),(j,i,1),(j,i,−1)(i,j,1) ,(i,j,-1),(j,i,1),(j,i,-1)(i,j,1),(i,j,−1),(j,i,1),(j,i,−1)。但是对于(i,j,1)(i,j,1)(i,j,1)转化成不等式j−i1j-i1j−i1把(i,j,−1)(i,j,-1)(i,j,−1)转成不等式j−i−1j-i-1j−i−1当第一个成立的时候第二个显然成立所以只保留第一个就行啦。 让后跑差分约束就好啦nnn比较小直接floydfloydfloyd跑顺便判断一下负环就好啦。 这里用并查集判断的二分图。
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N310,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
int g[N][N],p[N*2];int find(int x) { return xp[x]? x:p[x]find(p[x]); }bool check()
{for(int i1;in;i) if(find(i)find(in)) return true;return false;
}bool floyd()
{for(int k1;kn;k)for(int i1;in;i){for(int j1;jn;j)g[i][j]min(g[i][j],g[i][k]g[k][j]);if(g[i][i]0) return true;}return false;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%d,n,m);for(int i1;in*2;i) p[i]i;memset(g,0x3f,sizeof(g));for(int i1;in;i) g[i][i]0;for(int i1;im;i){int a,b,op; scanf(%d%d%d,a,b,op);g[a][b]1; g[b][a]-1;if(!op) g[b][a]1;p[find(a)]find(bn);p[find(an)]find(b);}if(check()||floyd()) { puts(NO); return 0; }int ans-1,id0;for(int i1;in;i){for(int j1;jn;j)if(g[i][j]ans) ansg[i][j],idi;}puts(YES);printf(%d\n,ans);for(int i1;in;i) printf(%d ,g[id][i]);return 0;
}
/**/