codeforces1149D Abandoning Roads
22906 단어 경전테크닉dp쌓다함께 조사하여 모으다
제면
제목의 뜻
한 장의 무방향도를 제시하는데, 각 변의 권한은 두 가지입니다: a 또는 b (a)
방법
우선 최소 생성 트리를 만들 때 값이 a인 변은 값이 b인 변보다 우선순위가 높기 때문에 모든 변이 a인 변을 축소할 수 있다. 그러면 값이 b인 변이 연결된 점이 같은 연결 블록에 있으면 이 변은 가치가 없다.그리고 만약에 하나의 경로가 특정한 연결 블록을 두 번 통과하면 이 경로가 최소 생성 트리에 나타날 수 없기 때문에 모든 연결 블록을 상압할 수 있다. dp[i][j]dp[i][j]dp[i][j]는 현재 점 i에 있음을 나타낸다. 지나간 연결 블록의 상태는 j의 최단거리 길이이지만 이런 상태수는 최대 n2n*2^n2n으로 지나갈 수 없다.다시 한 번 살펴보면 만약에 하나의 연결 블록 중의 포인트가 3을 초과하지 않는다면 어떤 경로가 그것을 두 번 지나가면 최단로가 아닐 것이다. 블록 안의 경로 길이가 최장 2a 2a이기 때문에 이런 연결 블록은 상태를 압축할 필요가 없다. 이런 상태 수는 최대 n2 n/4 n*2^ {n/4} n2n/4;로 가장 짧은 길로 해답을 구하면 된다.
코드 #include
#define N 80
#define M 150000
using namespace std;
int n,m,A,B,bb,tt,first[N],fa[N],num[N],sz[N],ans[N],dp[N][M];
struct Bn
{
int to,next,quan;
}bn[410];
struct Zt
{
int u,v,d;
bool operator < (const Zt &u) const{return d>u.d;}
};
priority_queue<Zt>pq;
int ff(int u){return fa[u]==u?u:fa[u]=ff(fa[u]);}
inline int get(int u){return num[u]==-1?0:(1 << num[u]);}
inline void add(int u,int v,int w)
{
bb++;
bn[bb].to=v;
bn[bb].quan=w;
bn[bb].next=first[u];
first[u]=bb;
}
int main()
{
memset(first,-1,sizeof(first));
memset(num,-1,sizeof(num));
memset(dp,0x3f,sizeof(dp));
memset(ans,0x3f,sizeof(ans));
int i,j,p,q,o;
cin>>n>>m>>A>>B;
for(i=1;i<=n;i++) fa[i]=i;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&p,&q,&o);
add(p,q,o),add(q,p,o);
if(o==A) fa[ff(p)]=ff(q);
}
for(i=1;i<=n;i++) sz[ff(i)]++;
for(i=1;i<=n;i++) if(i==ff(i)&&sz[i]>3) num[i]=++tt;
for(i=1;i<=n;i++) num[i]=num[ff(i)];
dp[1][get(1)]=0;
pq.push((Zt){1,get(1),0});
for(;!pq.empty();)
{
Zt now=pq.top();
pq.pop();
if(dp[now.u][now.v]<now.d) continue;
ans[now.u]=min(ans[now.u],now.d);
for(p=first[now.u];p!=-1;p=bn[p].next)
{
q=bn[p].to;
if(bn[p].quan==B&&num[q]!=-1&&((1 << num[q])&now.v)) continue;
if(bn[p].quan==B&&ff(now.u)==ff(q)) continue;
int t=bn[p].quan+now.d;
if(t>=dp[q][get(q)|now.v]) continue;
dp[q][get(q)|now.v]=t;
pq.push((Zt){q,get(q)|now.v,t});
}
}
for(i=1;i<=n;i++) printf("%d ",ans[i]);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
2D 접두어 및
2차원 접두사와 행렬에 있는 임의의 사각형의 숫자를 계산하는 데 사용되는 숫자의 합은 두 개의 for로만 그 중의 모든 요소를 더하면 모든 사각형을 처리하는 데 시간이 초과되고 정확한 방법의 복잡도는 O(m*n)이다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
한 장의 무방향도를 제시하는데, 각 변의 권한은 두 가지입니다: a 또는 b (a)
방법
우선 최소 생성 트리를 만들 때 값이 a인 변은 값이 b인 변보다 우선순위가 높기 때문에 모든 변이 a인 변을 축소할 수 있다. 그러면 값이 b인 변이 연결된 점이 같은 연결 블록에 있으면 이 변은 가치가 없다.그리고 만약에 하나의 경로가 특정한 연결 블록을 두 번 통과하면 이 경로가 최소 생성 트리에 나타날 수 없기 때문에 모든 연결 블록을 상압할 수 있다. dp[i][j]dp[i][j]dp[i][j]는 현재 점 i에 있음을 나타낸다. 지나간 연결 블록의 상태는 j의 최단거리 길이이지만 이런 상태수는 최대 n2n*2^n2n으로 지나갈 수 없다.다시 한 번 살펴보면 만약에 하나의 연결 블록 중의 포인트가 3을 초과하지 않는다면 어떤 경로가 그것을 두 번 지나가면 최단로가 아닐 것이다. 블록 안의 경로 길이가 최장 2a 2a이기 때문에 이런 연결 블록은 상태를 압축할 필요가 없다. 이런 상태 수는 최대 n2 n/4 n*2^ {n/4} n2n/4;로 가장 짧은 길로 해답을 구하면 된다.
코드 #include
#define N 80
#define M 150000
using namespace std;
int n,m,A,B,bb,tt,first[N],fa[N],num[N],sz[N],ans[N],dp[N][M];
struct Bn
{
int to,next,quan;
}bn[410];
struct Zt
{
int u,v,d;
bool operator < (const Zt &u) const{return d>u.d;}
};
priority_queue<Zt>pq;
int ff(int u){return fa[u]==u?u:fa[u]=ff(fa[u]);}
inline int get(int u){return num[u]==-1?0:(1 << num[u]);}
inline void add(int u,int v,int w)
{
bb++;
bn[bb].to=v;
bn[bb].quan=w;
bn[bb].next=first[u];
first[u]=bb;
}
int main()
{
memset(first,-1,sizeof(first));
memset(num,-1,sizeof(num));
memset(dp,0x3f,sizeof(dp));
memset(ans,0x3f,sizeof(ans));
int i,j,p,q,o;
cin>>n>>m>>A>>B;
for(i=1;i<=n;i++) fa[i]=i;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&p,&q,&o);
add(p,q,o),add(q,p,o);
if(o==A) fa[ff(p)]=ff(q);
}
for(i=1;i<=n;i++) sz[ff(i)]++;
for(i=1;i<=n;i++) if(i==ff(i)&&sz[i]>3) num[i]=++tt;
for(i=1;i<=n;i++) num[i]=num[ff(i)];
dp[1][get(1)]=0;
pq.push((Zt){1,get(1),0});
for(;!pq.empty();)
{
Zt now=pq.top();
pq.pop();
if(dp[now.u][now.v]<now.d) continue;
ans[now.u]=min(ans[now.u],now.d);
for(p=first[now.u];p!=-1;p=bn[p].next)
{
q=bn[p].to;
if(bn[p].quan==B&&num[q]!=-1&&((1 << num[q])&now.v)) continue;
if(bn[p].quan==B&&ff(now.u)==ff(q)) continue;
int t=bn[p].quan+now.d;
if(t>=dp[q][get(q)|now.v]) continue;
dp[q][get(q)|now.v]=t;
pq.push((Zt){q,get(q)|now.v,t});
}
}
for(i=1;i<=n;i++) printf("%d ",ans[i]);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
2D 접두어 및
2차원 접두사와 행렬에 있는 임의의 사각형의 숫자를 계산하는 데 사용되는 숫자의 합은 두 개의 for로만 그 중의 모든 요소를 더하면 모든 사각형을 처리하는 데 시간이 초과되고 정확한 방법의 복잡도는 O(m*n)이다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include
#define N 80
#define M 150000
using namespace std;
int n,m,A,B,bb,tt,first[N],fa[N],num[N],sz[N],ans[N],dp[N][M];
struct Bn
{
int to,next,quan;
}bn[410];
struct Zt
{
int u,v,d;
bool operator < (const Zt &u) const{return d>u.d;}
};
priority_queue<Zt>pq;
int ff(int u){return fa[u]==u?u:fa[u]=ff(fa[u]);}
inline int get(int u){return num[u]==-1?0:(1 << num[u]);}
inline void add(int u,int v,int w)
{
bb++;
bn[bb].to=v;
bn[bb].quan=w;
bn[bb].next=first[u];
first[u]=bb;
}
int main()
{
memset(first,-1,sizeof(first));
memset(num,-1,sizeof(num));
memset(dp,0x3f,sizeof(dp));
memset(ans,0x3f,sizeof(ans));
int i,j,p,q,o;
cin>>n>>m>>A>>B;
for(i=1;i<=n;i++) fa[i]=i;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&p,&q,&o);
add(p,q,o),add(q,p,o);
if(o==A) fa[ff(p)]=ff(q);
}
for(i=1;i<=n;i++) sz[ff(i)]++;
for(i=1;i<=n;i++) if(i==ff(i)&&sz[i]>3) num[i]=++tt;
for(i=1;i<=n;i++) num[i]=num[ff(i)];
dp[1][get(1)]=0;
pq.push((Zt){1,get(1),0});
for(;!pq.empty();)
{
Zt now=pq.top();
pq.pop();
if(dp[now.u][now.v]<now.d) continue;
ans[now.u]=min(ans[now.u],now.d);
for(p=first[now.u];p!=-1;p=bn[p].next)
{
q=bn[p].to;
if(bn[p].quan==B&&num[q]!=-1&&((1 << num[q])&now.v)) continue;
if(bn[p].quan==B&&ff(now.u)==ff(q)) continue;
int t=bn[p].quan+now.d;
if(t>=dp[q][get(q)|now.v]) continue;
dp[q][get(q)|now.v]=t;
pq.push((Zt){q,get(q)|now.v,t});
}
}
for(i=1;i<=n;i++) printf("%d ",ans[i]);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
2D 접두어 및2차원 접두사와 행렬에 있는 임의의 사각형의 숫자를 계산하는 데 사용되는 숫자의 합은 두 개의 for로만 그 중의 모든 요소를 더하면 모든 사각형을 처리하는 데 시간이 초과되고 정확한 방법의 복잡도는 O(m*n)이다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.