HDU 4370 0 or 1(最短)
16697 ワード
0 or 1
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 692 Accepted Submission(s): 185
Problem Description
Given a n*n matrix C
ij (1<=i,j<=n),We want to find a n*n matrix X
ij (1<=i,j<=n),which is 0 or 1.
Besides,X
ij meets the following conditions:
1.X
12+X
13+...X
1n=1
2.X
1n+X
2n+...X
n-1n=1
3.for each i (1ki (1<=k<=n)=∑X
ij (1<=j<=n).
For example, if n=4,we can get the following equality:
X
12+X
13+X
14=1
X
14+X
24+X
34=1
X
12+X
22+X
32+X
42=X
21+X
22+X
23+X
24
X
13+X
23+X
33+X
43=X
31+X
32+X
33+X
34
Now ,we want to know the minimum of ∑C
ij*X
ij(1<=i,j<=n) you can get.
Hint
For sample, X
12=X
24=1,all other X
ij is 0.
Input
The input consists of multiple test cases (less than 35 case).
For each test case ,the first line contains one integer n (1The next n lines, for each lines, each of which contains n integers, illustrating the matrix C, The j-th integer on i-th line is C
ij(0<=C
ij<=100000).
Output
For each case, output the minimum of ∑C
ij*X
ij you can get.
Sample Input
4 1 2 4 10 2 0 1 1 2 2 0 5 6 3 1 2
Sample Output
3
Author
Snow_storm
Source
2012 Multi-University Training Contest 8
Recommend
zhuyuanchen520
1001 (更新された)明らかに、テーマは0/1計画モデルを与えている.
問題を解く鍵はこのモデルの本質をどのように見るかにある.
3つの条件は明らかに未知数の関係を描き、図論の角度から問題を考え、以下の3つの結論を得やすい.
1.X 12+X 13+…X 1 n=1で1番ノードの出度が1
2.X 1 n+X 2 n+…Xn-1 n=1でn番ノードの入度が1
3.ΣXki=ΣXijよって2~n-1番ノードの入度は出度に等しくなければならない
したがって,3つの条件は1番ノードからn番ノードへの経路に等価であるため,Xij=1はエッジ(i,j)を通過する必要があることを示し,その代価はCijである.Xij=0は、エッジ(i,j)を通過しないことを示す.Cijは負ではなく,問題の総コストが最小であることに気づいたので,最適な答えの経路は必ず単純な経路に対応することができる.
最終的に,辺権の隣接行列を直接読み込み,1〜nの最短路を1回走ればよい,最短路をpathと記す.
以上の場合をAとする
非常に非常に非常に非常に非常に申し訳ありませんが、単純なパスは十分な条件ですが、必要ありません.(困ったチームに深くお詫び申し上げます)
次のようなケースが漏れていますB:
1から出発して、1つのリング(少なくとも1つの点を通る、すなわち自環ではない)を歩いて、1に戻る.nから、リング(同理)を歩いて、nに戻ります.
検証しやすく、これはテーマの条件に合っています.そして、A‖Bはこの問題に要求される要件である.
エッジ重みは負ではないので,2つのリングは2つの単純なリングに対応する.
そのため、私たちは1から出発して、最小費用リングを探して、代価をc 1として、nから出発して、最小費用リングを探して、代価をc 2とします.(最短アルゴリズムで重み値を更新するときにレコードを1つ追加するだけでよい:if(i=S)cir=min(cir,dis[u]+g[u][i]))
だから最終答えはmin(path,c 1+c 2)
次はスタックで実現したSPFA
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 692 Accepted Submission(s): 185
Problem Description
Given a n*n matrix C
ij (1<=i,j<=n),We want to find a n*n matrix X
ij (1<=i,j<=n),which is 0 or 1.
Besides,X
ij meets the following conditions:
1.X
12+X
13+...X
1n=1
2.X
1n+X
2n+...X
n-1n=1
3.for each i (1
ij (1<=j<=n).
For example, if n=4,we can get the following equality:
X
12+X
13+X
14=1
X
14+X
24+X
34=1
X
12+X
22+X
32+X
42=X
21+X
22+X
23+X
24
X
13+X
23+X
33+X
43=X
31+X
32+X
33+X
34
Now ,we want to know the minimum of ∑C
ij*X
ij(1<=i,j<=n) you can get.
Hint
For sample, X
12=X
24=1,all other X
ij is 0.
Input
The input consists of multiple test cases (less than 35 case).
For each test case ,the first line contains one integer n (1
ij(0<=C
ij<=100000).
Output
For each case, output the minimum of ∑C
ij*X
ij you can get.
Sample Input
4 1 2 4 10 2 0 1 1 2 2 0 5 6 3 1 2
Sample Output
3
Author
Snow_storm
Source
2012 Multi-University Training Contest 8
Recommend
zhuyuanchen520
1001 (更新された)明らかに、テーマは0/1計画モデルを与えている.
問題を解く鍵はこのモデルの本質をどのように見るかにある.
3つの条件は明らかに未知数の関係を描き、図論の角度から問題を考え、以下の3つの結論を得やすい.
1.X 12+X 13+…X 1 n=1で1番ノードの出度が1
2.X 1 n+X 2 n+…Xn-1 n=1でn番ノードの入度が1
3.ΣXki=ΣXijよって2~n-1番ノードの入度は出度に等しくなければならない
したがって,3つの条件は1番ノードからn番ノードへの経路に等価であるため,Xij=1はエッジ(i,j)を通過する必要があることを示し,その代価はCijである.Xij=0は、エッジ(i,j)を通過しないことを示す.Cijは負ではなく,問題の総コストが最小であることに気づいたので,最適な答えの経路は必ず単純な経路に対応することができる.
最終的に,辺権の隣接行列を直接読み込み,1〜nの最短路を1回走ればよい,最短路をpathと記す.
以上の場合をAとする
非常に非常に非常に非常に非常に申し訳ありませんが、単純なパスは十分な条件ですが、必要ありません.(困ったチームに深くお詫び申し上げます)
次のようなケースが漏れていますB:
1から出発して、1つのリング(少なくとも1つの点を通る、すなわち自環ではない)を歩いて、1に戻る.nから、リング(同理)を歩いて、nに戻ります.
検証しやすく、これはテーマの条件に合っています.そして、A‖Bはこの問題に要求される要件である.
エッジ重みは負ではないので,2つのリングは2つの単純なリングに対応する.
そのため、私たちは1から出発して、最小費用リングを探して、代価をc 1として、nから出発して、最小費用リングを探して、代価をc 2とします.(最短アルゴリズムで重み値を更新するときにレコードを1つ追加するだけでよい:if(i=S)cir=min(cir,dis[u]+g[u][i]))
だから最終答えはmin(path,c 1+c 2)
/*
HDU 4370 0 or 1
， ，
， n ，1 1，
n 1， ， ，
1 n ， Xij=1
(i,j)， Cij。Xij=0 (i,j)。 Cij
， 。
， ， 1 n ， path。
B：
1 ， （ 1 ，
）， 1； n ， （ ）， n。
1 n 1， 0.
， 。
1 ， ， c1,
n ， ， c2。
（ ：if(i==S) cir=min(cir,dis[u]+g[u][i])）
min(path,c1+c2)
*/
/*
SPFA 。
。
SPFA 。
dist[start] INF。 ，
。
*/
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=330;
int cost[MAXN][MAXN];//
int dist[MAXN];
int que[MAXN];// ，
bool vis[MAXN];//
void SPFA(int start,int n)
{
int front=0,rear=0;
for(int v=1;v<=n;v++)//
{
if(v==start)// start ， dist[start] INF，
{
dist[v]=INF;
vis[v]=false;
}
else if(cost[start][v]!=INF)
{
dist[v]=cost[start][v];
que[rear++]=v;
vis[v]=true;
}
else// dist[start][v]==INF ，
{
dist[v]=INF;
vis[v]=false;
}
}
while(front!=rear)// ，
{
int u=que[front++];
for(int v=1;v<=n;v++)
{
if(dist[v]>dist[u]+cost[u][v])
{
dist[v]=dist[u]+cost[u][v];
if(!vis[v])//
{
vis[v]=true;
que[rear++]=v;
if(rear>=MAXN) rear=0;//
}
}
}
vis[u]=false;
if(front>=MAXN)front=0;
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
SPFA(1,n);
int ans=dist[n];//1 n
int loop1=dist[1];//1
SPFA(n,n);
int loopn=dist[n];//n
ans=min(ans,loop1+loopn);
printf("%d
",ans);
}
return 0;
}次はスタックで実現したSPFA
/*
SPFA，
*/
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=330;
const int INF=0x3f3f3f3f;
int cost[MAXN][MAXN];
int dist[MAXN];
int Q[MAXN];
bool vis[MAXN];
void SPFA(int start,int n)
{// ，
int top=0;
for(int v=1;v<=n;v++)
{
if(v==start)
{
dist[v]=INF;
vis[v]=false;
}
else
{
dist[v]=cost[start][v];
vis[v]=true;
Q[top++]=v;
}
}
while(top!=0)
{
int u=Q[--top];
for(int v=1;v<=n;v++)
{
if(dist[v]>dist[u]+cost[u][v])
{
dist[v]=dist[u]+cost[u][v];
if(!vis[v])
{
vis[v]=true;
Q[top++]=v;
}
}
}
vis[u]=false;
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
SPFA(1,n);
int ans=dist[n];//1 n
int loop1=dist[1];//1
SPFA(n,n);
int loopn=dist[n];//n
ans=min(ans,loop1+loopn);
printf("%d
",ans);
}
return 0;
}