找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2981|回复: 1
收起左侧

[米群网刷题小分队] [PAT-TOP] 1003 Universal Travel Sites

[复制链接]
发表于 5-3-2015 02:59 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
1003  Universal Travel Sites
话说这个题——我没读太明白,根据样例YY的,反正是各裸的网络流,用了模版,通过了……
注意 500是边数而不是点数,所以点应该不多……

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <string>
  4. #include <map>

  5. using namespace std;

  6. #define MAXN 1005
  7. #define inf 1000000000
  8. char s[10];
  9. map<string,int> id;

  10. int max_flow(int n,int mat[][MAXN],int source,int sink){
  11.         int v[MAXN],c[MAXN],p[MAXN],ret=0,i,j;
  12.         for (;;){
  13.                 for (i=0;i<n;i++)
  14.                         v【i】=c【i】=0;
  15.                 for (c[source]=inf;;){
  16.                         for (j=-1,i=0;i<n;i++)
  17.                                 if (!v【i】&&c【i】&&(j==-1||c【i】>c[j]))
  18.                                         j=i;
  19.                         if (j<0) return ret;
  20.                         if (j==sink) break;
  21.                         for (v[j]=1,i=0;i<n;i++)
  22.                                 if (mat[j]【i】>c【i】&&c[j]>c【i】)
  23.                                         c【i】=mat[j]【i】<c[j]?mat[j]【i】:c[j],p【i】=j;
  24.                 }
  25.                 for (ret+=j=c[i=sink];i!=source;i=p【i】)
  26.                         mat[p【i】]【i】-=j,mat【i】[p【i】]+=j;
  27.         }
  28. }

  29. int a[MAXN][MAXN];

  30. int get(string s) {
  31. map<string,int>::iterator t = id.find(s);
  32.         if (t == id.end()) {
  33.                 id.insert(make_pair(s, id.size()));
  34.                 return id.size() - 1;
  35.         }
  36.         return t->second;
  37. }


  38. int main() {
  39.         scanf("%s",s);
  40.         int source = get((string) s);
  41.         int m;
  42.         scanf("%s%d",s, &m);
  43.         int target = get((string) s);
  44.         for (;m;--m) {
  45.                 scanf("%s",s);
  46.                 int x = get((string) s);
  47.                 scanf("%s",s);
  48.                 int y = get((string) s);
  49.                 int z;
  50.                 scanf("%d",&z);
  51.                 if (z > a[x][y]) {
  52.                         a[x][y] = z;
  53.                 }
  54.         }
  55.         while (source == target);
  56.         printf("%d\n",max_flow(id.size(), a, source, target));
  57.         return 0;
  58. }
  59.                
复制代码



本帖被以下淘专辑推荐:

我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

0

主题

0

精华

0

积分

新米人

Rank: 1

积分
0
发表于 12-18-2015 07:04 AM | 显示全部楼层
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表