vijos题目描述最长之题23333

/*
这个题目描述窝给满分...
醉了醉了~好长啊看吐血了
但是实际很简单的
首先说明一下每个点的时限其实是2s的(其实这个做法开了map都照样1ms稳过)
我们需要将每个IP地址转换成一个正整数方便解题
那么我们可以用一个hash或者map来解决一下~
映射好之后我们还需要记录一下每个结点对应的ip值便于输出
然后注意读入的时候可能多次读入一个ip
那么还要累加起来
然后读入边了
当且仅当边的两个端点在上面出现过
窝们连一条无向边    权值就是两个顶点的权值之和
那么我们就可以枚举所有的n点
跑一边SPFA
(我们看到输入的n和m的最大范围相等~而且会有无效边，那么稀疏图SPFA更优而且好写)
然后再记录一下这个点到所有点的最短路径长度之和
然后累加    这里如果发现某个点不可达那么可以直接返回-INF
因为要求的点必然到所有点是要连通的
然后排个序就好啦~
细节还是要注意一下的  SPFA写了这么多次还是忘记少写了个in[u]=0然后WA了一发...
好弱啊~NOIP求rp++
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <map>
using namespace std;

const int MAXN=100005;
const int INF=(1<<30)-1;
struct Edge
{
    int to,w,next;
}e[MAXN<<1];
int fisrt[MAXN];//Edge
struct node
{
    int cost,idx;
    bool operator < (const node&b)const
    {
        return cost>b.cost;
    }
}sco[MAXN];
int n,m,tot;
map<string,int> Hash;
int d[MAXN],in[MAXN];//SPFA
string ip[MAXN];
int w[MAXN];

inline void Add_Edge(int x,int y,int w)
{
    e[++tot].to=y;  e[tot].w=w;
    e[tot].next=fisrt[x];   fisrt[x]=tot;
}

void init()
{
    int k,tmp;
    string a,b;
    memset(fisrt,-1,sizeof(fisrt));
    cin>>k;
    for(int i=1;i<=k;i++)
    {
        cin>>a>>tmp;
        if(Hash[a])
            w[Hash[a]]+=tmp;
        else
        {
            Hash[a]=++n;
            ip[n]=a;
            w[Hash[a]]=tmp;
        }
    }
    cin>>k;
    for(int i=1;i<=k;i++)
    {
        cin>>a>>b;
        if(Hash[a]&&Hash[b])
            Add_Edge(Hash[a],Hash[b],w[Hash[a]]+w[Hash[b]]),
            Add_Edge(Hash[b],Hash[a],w[Hash[a]]+w[Hash[b]]);
    }
}

int SPFA(int s)
{
    queue<int> q;
    for(int i=1;i<=n;i++)
        d[i]=INF;
    memset(in,0,sizeof(in));
    d[s]=0; in[s]=1; q.push(s); 
    while(!q.empty())
    {
        int u=q.front();    q.pop();    in[u]=0;
        for(int i=fisrt[u];i!=-1;i=e[i].next)
        {
            int& v=e[i].to; int& w=e[i].w;
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                if(!in[v])
                    in[v]=1,q.push(v);
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(d[i]==INF)
            return -INF;
        else
            ans+=d[i];
    }
    return ans;
}

void out()
{
    cout<<"The ONLY truth is: it is you, ";
    if(sco[1].cost==-INF||sco[1].cost==sco[2].cost)
        cout<<"222.240.168.135"<<endl;
    else
        cout<<ip[sco[1].idx]<<endl;
}

int main()
{
    init();
    for(int i=1;i<=n;i++)
    {
        sco[i].cost=SPFA(i);
        sco[i].idx=i;
    }
    sort(sco+1,sco+n+1);
    out();
    return 0;
}
     

www.vijos.cn [222.240.168.135]

#include <bits/stdc++.h>
using namespace std;
const int MAXN=100005;
const int INF=(1<<30)-1;
struct Edge
{
int to,w,next;
}e[MAXN<<1];
int fisrt[MAXN];//Edge
struct node
{
int cost,idx;
bool operator < (const node&b)const
{
return cost>b.cost;
}
}sco[MAXN];
int n,m,tot;
map<string,int> Hash;
int d[MAXN],in[MAXN];//SPFA
string ip[MAXN];
int w[MAXN];

inline void Add_Edge(int x,int y,int w)
{
e[++tot].to=y; e[tot].w=w;
e[tot].next=fisrt[x]; fisrt[x]=tot;
}

void init()
{
int k,tmp;
string a,b;
memset(fisrt,-1,sizeof(fisrt));
cin>>k;
for(int i=1;i<=k;i++)
{
cin>>a>>tmp;
if(Hash[a])
w[Hash[a]]+=tmp;
else
{
Hash[a]=++n;
ip[n]=a;
w[Hash[a]]=tmp;
}
}
cin>>k;
for(int i=1;i<=k;i++)
{
cin>>a>>b;
if(Hash[a]&&Hash[b])
Add_Edge(Hash[a],Hash[b],w[Hash[a]]+w[Hash[b]]),
Add_Edge(Hash[b],Hash[a],w[Hash[a]]+w[Hash[b]]);
}
}

int SPFA(int s)
{
queue<int> q;
for(int i=1;i<=n;i++)
d[i]=INF;
memset(in,0,sizeof(in));
d[s]=0; in[s]=1; q.push(s);
while(!q.empty())
{
int u=q.front(); q.pop(); in[u]=0;
for(int i=fisrt[u];i!=-1;i=e[i].next)
{
int& v=e[i].to; int& w=e[i].w;
if(d[v]>d[u]+w)
{
d[v]=d[u]+w;
if(!in[v])
in[v]=1,q.push(v);
}
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(d[i]==INF)
return -INF;
else
ans+=d[i];
}
return ans;
}

void out()
{
cout<<"The ONLY truth is: it is you, ";
if(sco[1].cost==-INF||sco[1].cost==sco[2].cost)
cout<<"222.240.168.135"<<endl;
else
cout<<ip[sco[1].idx]<<endl;
}

int main()
{
init();
for(int i=1;i<=n;i++)
{
sco[i].cost=SPFA(i);
sco[i].idx=i;
}
sort(sco+1,sco+n+1);
out();
return 0;
}
//不对抽我

看题让我十分爽快，还好ac了

#include <map>
#include <queue>
#include <cstdio>
#include <cstring>
#include <climits>
#include <iostream>
#include <algorithm>
#define MAXN 2010
#define MAXM 80010
using namespace std;

struct node
{
int pt;
long long best_dis;
};

bool cmp(node a,node b)
{
return a.best_dis>b.best_dis;
}

int ip_num,n,m;
int tmp;
string ip[MAXN],tmpip;
int dist[MAXN];
bool vis[MAXN];
int a[MAXN];
int head[MAXN],nex[MAXM],to[MAXM],cnt = 0;
int wei[MAXM];
node best[MAXN];
map <string,int> hash_table;
queue <int> q;

int spfa(int src)
{
while (!q.empty()) q.pop();
q.push(src);
memset(vis, false, sizeof(vis));
for (int i=1;i<=n;i++)
dist[i]=INT_MAX;
vis[src]=true;dist[src]=0;
while(!q.empty())
{
int u = q.front();
q.pop(); vis[u] = false;
for(int i = head[u]; i != -1; i = nex[i])
{
int v = to[i];
if(v == 0) continue;
if(dist[v] > dist[u] + wei[i])
{
dist[v] = dist[u] + wei[i];
if(!vis[v])
{
q.push(v);
vis[v] = true;
}
}
}
}
int ans=0;
for (int i=1;i<=n;i++)
{
if (dist[i]==INT_MAX)
return INT_MAX;
else ans+=dist[i];
}
return ans;
}

void add(int u, int v, long long w)
{
nex[cnt] = head[u];
to[cnt] = v;
wei[cnt] = w;
head[u] = cnt++;
}

int main()
{
memset(head,-1,sizeof(head));
cin>>ip_num;
for (int i=1;i<=ip_num;i++)
{
cin>>tmpip>>tmp;
if (hash_table[tmpip])
a[hash_table[tmpip]]+=tmp;
else
{
n++;
hash_table[tmpip]=n;
a[hash_table[tmpip]]=tmp;
ip[n]=tmpip;
}
}
cin>>m;
for (int i=1;i<=m;i++)
{
string tmp1,tmp2;
cin>>tmp1>>tmp2;
if (hash_table[tmp1]&&hash_table[tmp2])
{
add(hash_table[tmp1],hash_table[tmp2],a[hash_table[tmp1]]+a[hash_table[tmp2]]);
add(hash_table[tmp2],hash_table[tmp1],a[hash_table[tmp1]]+a[hash_table[tmp2]]);
}
}
for (int i=1;i<=n;i++)
{
best[i].best_dis=spfa(i);
best[i].pt=i;
}
sort(best+1,best+n+1,cmp);
if (best[1].best_dis==INT_MAX||best[1].best_dis==best[2].best_dis)
printf("The ONLY truth is: it is you, 222.240.168.135\n");
else
{
printf("The ONLY truth is: it is you, ");
cout<<ip[best[1].pt]<<endl;
}
return 0;
}

第8点怎么回事，有人能够解释一下吗？是std爆int了吗？

为啥longint能过，qword过不了呢？纠结！

我的程序怎么没有了

我是第13个

ELFHASH对这题不太适用,IP判重最好用字母树(Tire)

这里把树的深度限定为4,深度为X的节点就是IP的第X段

因为最多2000个IP,所以TIRE及其SON数组大概开8000*256就够了

以上是预处理

SPFA求解,感觉要比DIJK快

MS有点对点之间的Joneson算法,可以快很多

折腾了一天，总觉得是SPFA不够快，找了各种优化办法都超时

终于发现是hash函数浪费时间了

一般的字符串比较太慢了

既然数据是IP地址那就用数字来存，这样比较起来就快多了

（原来的hash函数最后2个点超时，换了新的以后就是0s了……）

柯南再一次和组织擦肩而过, 命运之轮继续旋转………

题目描述很有感觉

ELFHASH＋SPFA吧...

呼。。

第41个。。。

请问这题的HASH是怎么转的？

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 72ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 150ms

├ 测试数据 10：答案正确... 103ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：334ms

我的堆优化的ＤＩＪＫＳＴＲＡ啊．．饿　被删了

注意同一IP地址可能投放多次包

我晕，竟然没看见

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 119ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 72ms

├ 测试数据 07：答案正确... 447ms

├ 测试数据 08：答案正确... 72ms

├ 测试数据 09：答案正确... 338ms

├ 测试数据 10：答案正确... 447ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1495ms

原来就是最短路啊，之前还以为会超时呢

注意同一IP地址可能投放多次包, 至多不超过2000个IP地址

spfa可解

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 228ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 88ms

├ 测试数据 08：答案正确... 88ms

├ 测试数据 09：答案正确... 962ms

├ 测试数据 10：答案正确... 1041ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2407ms

我用的是SPFA,看来有时候这东西还挺慢的.

小朋友用 血的事实说明, spfa绝对比nlogn Dijkstra好使.....

vijos风气日下啊……

题意就是以输入数据前半段出现过的ip为顶点，边的权值设为两顶点的权值和，求一个顶点，使得它到其它点的最短路径之和大于其他所有顶点的这个属性。如果不存在这样的点（有多个最大值，或者图不连通），输出vj的ip

做法么……用Hash转换ip，用链表存边，用堆做Dijkstra，大略如此，无啥新意

话说偶因为heap写错浪费了好几十分钟的脑细胞来着。。。

话说偶没处理非连通图居然都ac来着。。。