题目链接: https://cn.vjudge.net/problem/HDU-4370
题意
给一个矩阵 C(nn), 要我们找到一个矩阵 X(nn), 满足以下条件:
- X_{12}+X_{13}+...X_{1n}=1
- X_{1n}+X_{2n}+...X_{n-1n}=1
for each i (1<i<n), satisfies X_{ki} (1<=k<=n)=X_{ij} (1<=j<=n).
min C ij*X ij
思路
如果把 X 当成一个邻接矩阵, 可以发现本题就是要找一个图, 满足以下条件:
节点 1 有一个出度 (注意不要 1->1, 因为要最小化边权), 节点 n 有一个入度 (同理不要 n->n)
其他节点出度等于入度
最小化边权
很容易发现最短路是一种可能的情况 (每个节点仅有一个出度入度)
另外还有一种情况需要考虑, 就是起点和终点可以不连通, 意思就是节点 1 节点 n 各参与一个互不连通的环
这还是要考虑连通问题啊
又没考虑, 可烦, 考虑开一个最短路专题总结一下
提交过程
WA1 | 没考虑连通性 |
WA2 | int 换 long long |
WA3 | 脑抽加上了 1->1 和 n->n 情况 |
代码
- #include <queue>
- #include <cstdio>
- #include <cstring>
- using namespace std;
- const int maxn=320;
- const long long INF=1LL<<60;
- typedef pair<long long, int> Node;
- struct Cmp{
- bool operator () (const Node &a, const Node &b){
- return a.first>b.first;
- }
- };
- int G[maxn+5][maxn+5];
- long long Dij(int n){
- long long dist[maxn+5], ans=0, circle1=INF, circle2=INF;
- priority_queue<Node, vector<Node>, Cmp> que;
- for (int i=0;i<=n; i++) dist[i]=INF;
- dist[1]=0;
- que.push(Node(dist[1], 1));
- while (que.size()){
- Node x=que.top(); que.pop();
- if (x.first!=dist[x.second]) continue;
- int &from=x.second;
- for (int to=1; to<=n; to++) if (to!=from){
- int &dis=G[from][to];
- if (to==1) circle1=min(circle1, dist[from]+dis);
- if (dist[to]<=dist[from]+(long long)dis) continue;
- dist[to]=dist[from]+(long long)dis;
- que.push(Node(dist[to], to));
- }
- }//return dist[n];
- ans=dist[n];
- for (int i=0;i<=n; i++) dist[i]=INF;
- dist[n]=0;
- que.push(Node(dist[n], n));
- while (que.size()){
- Node x=que.top(); que.pop();
- if (x.first!=dist[x.second]) continue;
- int &from=x.second;
- for (int to=1; to<=n; to++) if (to!=from){
- int &dis=G[from][to];
- if (to==n) circle2=min(circle2, dist[from]+dis);
- if (dist[to]<=dist[from]+(long long)dis) continue;
- dist[to]=dist[from]+(long long)dis;
- que.push(Node(dist[to], to));
- }
- }return min(ans, circle1+circle2);
- }
- int main(void){
- int n;
- while (scanf("%d", &n)==1 && n){
- for (int y=1; y<=n; y++)
- for (int x=1; x<=n; x++) scanf("%d", &G[y][x]);
- printf("%lld\n", Dij(n));
- }
- return 0;
- }
Time | Memory | Length | Lang | Submitted |
---|---|---|---|---|
1107ms | 2012kB | 1790 | G++ | 2018-06-02 11:28:23 |
来源: http://www.bubuko.com/infodetail-2637263.html