PKU2019数据结构与算法实习模板

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, k, ans;
int fa[50005], w[50005];
int getfa(int x)
{
    if(x == fa[x])return x;
    int t = fa[x]; fa[x] = getfa(fa[x]);
    w[x] = (w[x] + w[t]) % 3;
    return fa[x];
}
int main()
{
    n = read(); k = read();
    for(int i = 1; i <= n; i++)
        fa[i] = i;        
    for(int i = 1; i <= k; i++)
    {
        int d = read(), x = read(), y = read();
        if(x > n || y > n || (x == y && d == 2))
            ans++;
        else
        {
            int fx = getfa(x), fy = getfa(y);
            if(fx == fy)
            {
                if(d == 1 && w[x] != w[y])ans++;
                else if(d == 2 && (w[x] + 1) % 3 != w[y])ans++;
            }
            else
            {
                fa[fy] = fx;
                w[fy] = (d - 1 + w[x] - w[y] + 3) % 3;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n, k, ans;

int fa[50005], w[50005];

int getfa(int x)

{

if(x == fa[x])return x;

int t = fa[x]; fa[x] = getfa(fa[x]);

w[x] = (w[x] + w[t]) % 3;

return fa[x];

}

int main()

{

n = read(); k = read();

for(int i = 1; i <= n; i++)

fa[i] = i;

for(int i = 1; i <= k; i++)

{

int d = read(), x = read(), y = read();

if(x > n || y > n || (x == y && d == 2))

ans++;

else

{

int fx = getfa(x), fy = getfa(y);

if(fx == fy)

{

if(d == 1 && w[x] != w[y])ans++;

else if(d == 2 && (w[x] + 1) % 3 != w[y])ans++;

}

else

{

fa[fy] = fx;

w[fy] = (d - 1 + w[x] - w[y] + 3) % 3;

}

printf("%d\n", ans);

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m, s, cnt;
double V, dis[105];
int q[105], last[105];
bool inq[105];
struct data{
    int to, next;
    double r, c;
}e[205];
void insert(int u, int v, double r, double c)
{
    e[++cnt] = (data){v, last[u], r, c}; last[u] = cnt;
}
bool spfa()
{   
    int head = 0, tail = 1;
    dis[s] = V; q[0] = s; inq[s] = 1;
    while(head != tail)
    {
        int x = q[head]; head++; if(head == 100)head = 0;
        for(int i = last[x]; i; i = e[i].next)
            if((dis[x] - e[i].c) * e[i].r > dis[e[i].to])
            {
                if(e[i].to == s)return 1;
                dis[e[i].to] = (dis[x] - e[i].c) * e[i].r;
                if(!inq[e[i].to])
                {
                    q[tail++] = e[i].to;
                    inq[e[i].to] = 1;
                }
                if(tail == 100)tail = 0;
            }        
        inq[x] = 0;
    }
    return 0;
}
int main()    
{
    n = read(); m = read(); s = read(); scanf("%lf", &V);
    for(int i = 1; i <= m; i++)
    {
        int u = read(), v = read();
        double R, C;
        scanf("%lf%lf", &R, &C);
        insert(u, v, R, C);
        scanf("%lf%lf", &R, &C);
        insert(v, u, R, C);
    }
    if(spfa())
        puts("YES");
    else
        puts("NO");
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n, m, s, cnt;

double V, dis[105];

int q[105], last[105];

bool inq[105];

struct data{

int to, next;

double r, c;

}e[205];

void insert(int u, int v, double r, double c)

{

e[++cnt] = (data){v, last[u], r, c}; last[u] = cnt;

}

bool spfa()

{

int head = 0, tail = 1;

dis[s] = V; q[0] = s; inq[s] = 1;

while(head != tail)

{

int x = q[head]; head++; if(head == 100)head = 0;

for(int i = last[x]; i; i = e[i].next)

if((dis[x] - e[i].c) * e[i].r > dis[e[i].to])

{

if(e[i].to == s)return 1;

dis[e[i].to] = (dis[x] - e[i].c) * e[i].r;

if(!inq[e[i].to])

{

q[tail++] = e[i].to;

inq[e[i].to] = 1;

}

if(tail == 100)tail = 0;

}

inq[x] = 0;

}

return 0;

}

int main()

{

n = read(); m = read(); s = read(); scanf("%lf", &V);

for(int i = 1; i <= m; i++)

{

int u = read(), v = read();

double R, C;

scanf("%lf%lf", &R, &C);

insert(u, v, R, C);

scanf("%lf%lf", &R, &C);

insert(v, u, R, C);

}

if(spfa())

puts("YES");

else

puts("NO");

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m, ind, top, scc, ans;
int dfn[10005], low[10005], inq[10005], q[10005], bl[10005], size[10005], d[10005];
int u[50005], v[50005];
vector<int> e[10005];
void tarjan(int x)
{
    dfn[x] = low[x] = ++ind;
    q[++top] = x;
    inq[x] = 1;
    for(int i = 0; i < e[x].size(); i++)
        if(!dfn[e[x][i]])
        {
            tarjan(e[x][i]);
            low[x] = min(low[x], low[e[x][i]]);
        }
        else if(inq[e[x][i]])
            low[x] = min(low[x], dfn[e[x][i]]);
    if(dfn[x] == low[x])
    {
        int now = -1; scc++;
        while(now != x)
        {
            now = q[top]; top--;
            inq[now] = 0;
            bl[now] = scc;
            size[scc]++;
        }
    }
}
int main()
{
    n = read(); m = read();
    for(int i = 1; i <= m; i++)
    {
        u[i] = read(), v[i] = read();
        e[v[i]].push_back(u[i]);
    }
    for(int i = 1; i <= n; i++)
        if(!dfn[i])
            tarjan(i);
    for(int i = 1; i <= m; i++)
        if(bl[u[i]] != bl[v[i]])
            d[bl[u[i]]]++;
    for(int i = 1; i <= scc; i++)
    {
        if(d[i] == 0)
        {
            if(ans)
            {
                ans = 0;
                break;
            }
            ans = size[i];            
        }
    }
    printf("%d\n", ans);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n, m, ind, top, scc, ans;

int dfn[10005], low[10005], inq[10005], q[10005], bl[10005], size[10005], d[10005];

int u[50005], v[50005];

vector<int> e[10005];

void tarjan(int x)

{

dfn[x] = low[x] = ++ind;

q[++top] = x;

inq[x] = 1;

for(int i = 0; i < e[x].size(); i++)

if(!dfn[e[x][i]])

{

tarjan(e[x][i]);

low[x] = min(low[x], low[e[x][i]]);

}

else if(inq[e[x][i]])

low[x] = min(low[x], dfn[e[x][i]]);

if(dfn[x] == low[x])

{

int now = -1; scc++;

while(now != x)

{

now = q[top]; top--;

inq[now] = 0;

bl[now] = scc;

size[scc]++;

}

int main()

{

n = read(); m = read();

for(int i = 1; i <= m; i++)

{

u[i] = read(), v[i] = read();

e[v[i]].push_back(u[i]);

}

for(int i = 1; i <= n; i++)

if(!dfn[i])

tarjan(i);

for(int i = 1; i <= m; i++)

if(bl[u[i]] != bl[v[i]])

d[bl[u[i]]]++;

for(int i = 1; i <= scc; i++)

{

if(d[i] == 0)

{

if(ans)

{

ans = 0;

break;

}

ans = size[i];

}

printf("%d\n", ans);

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T, n, ans;
int x[10005], y[10005], a[20005], vis[10005];
int l[100005], r[100005], c[100005];
void build(int k, int x, int y)
{
    int mid = (x + y) >> 1;    
    c[k] = 0; l[k] = x; r[k] = y;
    if(x == y)return;
    build(k << 1, x, mid);
    build(k << 1 | 1, mid + 1, y);
}
void modify(int k, int x, int y, int v)
{
    int L = l[k], R = r[k], mid = (L + R) >> 1;
    if(c[k] && L != R)
    {
        c[k << 1] = c[k];
        c[k << 1 | 1] = c[k];
        c[k] = 0;
    }
    if(L == x && y == R)
    {
        c[k] = v;
        return;
    }
    if(x <= mid)
        modify(k << 1, x, min(mid, y), v);
    if(y > mid)
        modify(k << 1 | 1, max(x, mid + 1), y, v);
}
int query(int k, int x)
{
    int L = l[k], R = r[k], mid = (L + R) >> 1;
    if(c[k] || L == R)
        return c[k];
    if(x <= mid)
        return query(k << 1, x);
    else return query(k << 1 | 1, x);
}
void dfs(int k)
{
    if(c[k])
    {
        if(!vis[c[k]])
        {
            ans++;
            vis[c[k]] = 1;
        }
        return;
    }
    if(l[k] == r[k])return;
    dfs(k << 1);
    dfs(k << 1 | 1);
}
int main()  
{
    T = read();
    while(T--)        
    {
        n = read();
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= n; i++)
        {
            x[i] = read(), y[i] = read();
            a[2 * i] = x[i];
            a[2 * i - 1] = y[i];
        }
        sort(a + 1, a + 2 * n + 1);
        for(int i = 1; i <= n; i++)
        {
            x[i] = lower_bound(a + 1, a + 2 * n + 1, x[i]) - a;
            y[i] = lower_bound(a + 1, a + 2 * n + 1, y[i]) - a;
        }
        build(1, 1, 2 * n);
        for(int i = 1; i <= n; i++)
            modify(1, x[i], y[i], i);
        ans = 0;
        dfs(1);
        cout << ans << endl;
    }
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int T, n, ans;

int x[10005], y[10005], a[20005], vis[10005];

int l[100005], r[100005], c[100005];

void build(int k, int x, int y)

{

int mid = (x + y) >> 1;

c[k] = 0; l[k] = x; r[k] = y;

if(x == y)return;

build(k << 1, x, mid);

build(k << 1 | 1, mid + 1, y);

}

void modify(int k, int x, int y, int v)

{

int L = l[k], R = r[k], mid = (L + R) >> 1;

if(c[k] && L != R)

{

c[k << 1] = c[k];

c[k << 1 | 1] = c[k];

c[k] = 0;

}

if(L == x && y == R)

{

c[k] = v;

return;

}

if(x <= mid)

modify(k << 1, x, min(mid, y), v);

if(y > mid)

modify(k << 1 | 1, max(x, mid + 1), y, v);

}

int query(int k, int x)

{

int L = l[k], R = r[k], mid = (L + R) >> 1;

if(c[k] || L == R)

return c[k];

if(x <= mid)

return query(k << 1, x);

else return query(k << 1 | 1, x);

}

void dfs(int k)

{

if(c[k])

{

if(!vis[c[k]])

{

ans++;

vis[c[k]] = 1;

}

return;

}

if(l[k] == r[k])return;

dfs(k << 1);

dfs(k << 1 | 1);

}

int main()

{

T = read();

while(T--)

{

n = read();

memset(vis, 0, sizeof(vis));

for(int i = 1; i <= n; i++)

{

x[i] = read(), y[i] = read();

a[2 * i] = x[i];

a[2 * i - 1] = y[i];

}

sort(a + 1, a + 2 * n + 1);

for(int i = 1; i <= n; i++)

{

x[i] = lower_bound(a + 1, a + 2 * n + 1, x[i]) - a;

y[i] = lower_bound(a + 1, a + 2 * n + 1, y[i]) - a;

}

build(1, 1, 2 * n);

for(int i = 1; i <= n; i++)

modify(1, x[i], y[i], i);

ans = 0;

dfs(1);

cout << ans << endl;

}

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m, cnt = 1;
char s[1005];
int t[200005][26], q[200005], danger[200005], fail[200005];
void insert(int l)
{
    int now = 1;
    for(int i = 0; i < l; i++)
    {
        int x = s[i] - 'a';
        if(!t[now][x])
            t[now][x] = ++cnt;
        now = t[now][x];
    }
    danger[now] = 1;
}
void buildfail()
{
    int head = 0, tail = 1;
    q[0] = 1; fail[1] = 0;
    for(int i = 0; i < 26; i++)
        t[0][i] = 1;
    while(head != tail)
    {
        int x = q[head]; head++;
        for(int i = 0; i < 26; i++)
        {
            int y = t[x][i], k = fail[x];
            if(!y)continue;
            while(!t[k][i])
                k = fail[k];
            fail[y] = t[k][i];
            q[tail++] = y;
        }
        danger[x] |= danger[fail[x]];
    }    
}
bool query(int l)
{
    int now = 1;
    for(int i = 0; i < l; i++)
    {
        int x = s[i] - 'a';
        while(!t[now][x])
            now = fail[now];
        now = t[now][x];
        if(danger[now])return 1;
    }
    return 0;
}
int main()
{
    n = read();
    for(int i = 1; i <= n; i++)
    {
        scanf("%s", s);
        insert(strlen(s));
    }
    buildfail();
    m = read();
    for(int i = 1; i <= m; i++)
    {
        scanf("%s", s);
        if(query(strlen(s)))puts("YES");
        else puts("NO");
    }    
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n, m, cnt = 1;

char s[1005];

int t[200005][26], q[200005], danger[200005], fail[200005];

void insert(int l)

{

int now = 1;

for(int i = 0; i < l; i++)

{

int x = s[i] - 'a';

if(!t[now][x])

t[now][x] = ++cnt;

now = t[now][x];

}

danger[now] = 1;

}

void buildfail()

{

int head = 0, tail = 1;

q[0] = 1; fail[1] = 0;

for(int i = 0; i < 26; i++)

t[0][i] = 1;

while(head != tail)

{

int x = q[head]; head++;

for(int i = 0; i < 26; i++)

{

int y = t[x][i], k = fail[x];

if(!y)continue;

while(!t[k][i])

k = fail[k];

fail[y] = t[k][i];

q[tail++] = y;

}

danger[x] |= danger[fail[x]];

}

bool query(int l)

{

int now = 1;

for(int i = 0; i < l; i++)

{

int x = s[i] - 'a';

while(!t[now][x])

now = fail[now];

now = t[now][x];

if(danger[now])return 1;

}

return 0;

}

int main()

{

n = read();

for(int i = 1; i <= n; i++)

{

scanf("%s", s);

insert(strlen(s));

}

buildfail();

m = read();

for(int i = 1; i <= m; i++)

{

scanf("%s", s);

if(query(strlen(s)))puts("YES");

else puts("NO");

}

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, K, C, M, cnt, ans;
int h[305], last[305], q[305];
int a[305][305];
struct data{
    int to, next, v;
}e[1000005];
void insert(int u, int v, int w)
{
    e[++cnt].to = v; e[cnt].next = last[u]; last[u] = cnt; e[cnt].v = w;
    e[++cnt].to = u; e[cnt].next = last[v]; last[v] = cnt; e[cnt].v = 0;
}
bool bfs()
{
    int head = 0, tail = 1;
    memset(h, 0, sizeof(h));
    h[0] = 1; 
    while(head != tail)
    {
        int x = q[head]; head++;
        for(int i = last[x]; i; i = e[i].next)
            if(e[i].v && !h[e[i].to])
            {
                h[e[i].to] = h[x] + 1;
                q[tail++] = e[i].to;
            }
    }
    return h[n + 1];
}
int dfs(int x, int f)
{
    int w, used = 0;
    if(x == n + 1)return f;
    for(int i = last[x]; i; i = e[i].next)
        if(h[e[i].to] == h[x] + 1)
        {
            w = dfs(e[i].to, min(e[i].v, f - used));
            e[i].v -= w; e[i ^ 1].v += w;
            used += w;
            if(used == f)return f;
        }
    if(!used)h[x] = 0;
    return used;
}
bool check(int x)
{
    memset(last, 0, sizeof(last));
    cnt = 1;
    for(int i = 1; i <= K; i++)
        for(int j = K + 1; j <= n; j++)
            if(a[i][j] <= x)
                insert(i, j, inf);
    for(int i = 1; i <= K; i++)
        insert(0, i, M);
    for(int i = 1; i <= C; i++)
        insert(K + i, n + 1, 1);
    ans = 0;
    while(bfs())
        ans += dfs(0, inf);
    return ans == C;
}
int main()
{
    memset(a, 127 / 3, sizeof(a));
    K = read(); C = read(); M = read();
    n = K + C;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            int x = read();
            if(x)a[i][j] = x;
        }
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
    int l = 0, r = 1000000, mid, ans = -1;
    while(l <= r)
    {
        mid = (l + r) >> 1;
        if(check(mid))ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << ans << endl;
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n, K, C, M, cnt, ans;

int h[305], last[305], q[305];

int a[305][305];

struct data{

int to, next, v;

}e[1000005];

void insert(int u, int v, int w)

{

e[++cnt].to = v; e[cnt].next = last[u]; last[u] = cnt; e[cnt].v = w;

e[++cnt].to = u; e[cnt].next = last[v]; last[v] = cnt; e[cnt].v = 0;

}

bool bfs()

{

int head = 0, tail = 1;

memset(h, 0, sizeof(h));

h[0] = 1;

while(head != tail)

{

int x = q[head]; head++;

for(int i = last[x]; i; i = e[i].next)

if(e[i].v && !h[e[i].to])

{

h[e[i].to] = h[x] + 1;

q[tail++] = e[i].to;

}

return h[n + 1];

}

int dfs(int x, int f)

{

int w, used = 0;

if(x == n + 1)return f;

for(int i = last[x]; i; i = e[i].next)

if(h[e[i].to] == h[x] + 1)

{

w = dfs(e[i].to, min(e[i].v, f - used));

e[i].v -= w; e[i ^ 1].v += w;

used += w;

if(used == f)return f;

}

if(!used)h[x] = 0;

return used;

}

bool check(int x)

{

memset(last, 0, sizeof(last));

cnt = 1;

for(int i = 1; i <= K; i++)

for(int j = K + 1; j <= n; j++)

if(a[i][j] <= x)

insert(i, j, inf);

for(int i = 1; i <= K; i++)

insert(0, i, M);

for(int i = 1; i <= C; i++)

insert(K + i, n + 1, 1);

ans = 0;

while(bfs())

ans += dfs(0, inf);

return ans == C;

}

int main()

{

memset(a, 127 / 3, sizeof(a));

K = read(); C = read(); M = read();

n = K + C;

for(int i = 1; i <= n; i++)

for(int j = 1; j <= n; j++)

{

int x = read();

if(x)a[i][j] = x;

}

for(int k = 1; k <= n; k++)

for(int i = 1; i <= n; i++)

for(int j = 1; j <= n; j++)

a[i][j] = min(a[i][j], a[i][k] + a[k][j]);

int l = 0, r = 1000000, mid, ans = -1;

while(l <= r)

{

mid = (l + r) >> 1;

if(check(mid))ans = mid, r = mid - 1;

else l = mid + 1;

}

cout << ans << endl;

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m, K;
int height[1000005], Rank[1000005], s[1000005], pos[1000005];
char ans[205];
int wa[1000005], wb[1000005], wv[1000005], Ws[1000005];
int sa[1000005];
bool vis[4005];
void BuildSA() {
    int i, j, p, *pm = wa, *k2sa = wb, *t;
    for (i = 0; i<m; i++) Ws[i] = 0;
    for (i = 0; i<n; i++) Ws[pm[i] = s[i]]++;
    for (i = 1; i<m; i++) Ws[i] += Ws[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--Ws[pm[i]]] = i; for (j = p = 1; p < n; j <<= 1, m = p) {
        for (p = 0, i = n - j; i < n; i++) k2sa[p++] = i;
        for (i = 0; i < n; i++) if (sa[i] >= j) k2sa[p++] = sa[i] - j; for (i = 0; i < m; i++) Ws[i] = 0;
        for (i = 0; i < n; i++) Ws[wv[i] = pm[k2sa[i]]]++;
        for (i = 1; i < m; i++) Ws[i] += Ws[i - 1];
        for (i = n - 1; i >= 0; i--) sa[--Ws[wv[i]]] = k2sa[i];
        for (t = pm, pm = k2sa, k2sa = t, pm[sa[0]] = 0, p = i = 1; i<n; i++) { int a = sa[i - 1], b = sa[i];
            if (k2sa[a] == k2sa[b] && a + j < n && b + j < n && k2sa[a + j] == k2sa[b + j])
                pm[sa[i]] = p - 1;
            else
                pm[sa[i]] = p++;
        }
    }
    return;
}
void BuildHeight() {    
    int i, j, k;
    for(int i = 0; i < n; ++i)
        Rank[sa[i]] =  i;
    height[0] = 0;
    for (i = k = 0; i < n - 1; height[Rank[i++]] = k)
        for (k ? k-- : 0, j = sa[Rank[i] - 1];
                  s[i+k]==s[j+k]; k++);
}
bool check(int mid)
{
    memset(vis, 0, sizeof(vis));
    int cnt = 0;
    for(int i = 1; i < n; i++)
    {
        if(height[i] < mid)
        {
            memset(vis, 0, sizeof(vis));
            cnt = 0;
            continue;
        }
        if(!vis[pos[sa[i]]])vis[pos[sa[i]]] = 1, cnt++;
        if(!vis[pos[sa[i - 1]]])vis[pos[sa[i - 1]]] = 1, cnt++;
        if(cnt == K)
        {
            for(int j = 0; j < mid; j++)
                ans[j] = s[sa[i] + j] + 'a' - 1;
            return 1;
        }
    }
    return 0;
}
int main()
{
    while(1)
    {
        K = read();
        if(!K)break;
        n = 0; m = 27;
        char str[205];
        for(int i = 1; i <= K; i++)
        {
            scanf("%s", str);
            int l = strlen(str);
            for(int j = 0; j < l; j++)
            {
                pos[n] = i;
                s[n++] = str[j] - 'a' + 1;
            }
            pos[n] = i;
            s[n++] = m++;
        }
        s[n++] = 0;
        BuildSA();
        BuildHeight();
        int l = 0, r = 200, ansl = 0;
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            if(check(mid))ansl = mid, l = mid + 1;
            else r = mid - 1;
        }
        if(!ansl)
            puts("IDENTITY LOST");
        else
        {
            for(int i = 0; i < ansl; i++)
                printf("%c", ans[i]);
            cout << endl;
        }
    }
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n, m, K;

int height[1000005], Rank[1000005], s[1000005], pos[1000005];

char ans[205];

int wa[1000005], wb[1000005], wv[1000005], Ws[1000005];

int sa[1000005];

bool vis[4005];

void BuildSA() {

int i, j, p, *pm = wa, *k2sa = wb, *t;

for (i = 0; i<m; i++) Ws[i] = 0;

for (i = 0; i<n; i++) Ws[pm[i] = s[i]]++;

for (i = 1; i<m; i++) Ws[i] += Ws[i - 1];

for (i = n - 1; i >= 0; i--) sa[--Ws[pm[i]]] = i; for (j = p = 1; p < n; j <<= 1, m = p) {

for (p = 0, i = n - j; i < n; i++) k2sa[p++] = i;

for (i = 0; i < n; i++) if (sa[i] >= j) k2sa[p++] = sa[i] - j; for (i = 0; i < m; i++) Ws[i] = 0;

for (i = 0; i < n; i++) Ws[wv[i] = pm[k2sa[i]]]++;

for (i = 1; i < m; i++) Ws[i] += Ws[i - 1];

for (i = n - 1; i >= 0; i--) sa[--Ws[wv[i]]] = k2sa[i];

for (t = pm, pm = k2sa, k2sa = t, pm[sa[0]] = 0, p = i = 1; i<n; i++) { int a = sa[i - 1], b = sa[i];

if (k2sa[a] == k2sa[b] && a + j < n && b + j < n && k2sa[a + j] == k2sa[b + j])

pm[sa[i]] = p - 1;

else

pm[sa[i]] = p++;

}

return;

}

void BuildHeight() {

int i, j, k;

for(int i = 0; i < n; ++i)

Rank[sa[i]] = i;

height[0] = 0;

for (i = k = 0; i < n - 1; height[Rank[i++]] = k)

for (k ? k-- : 0, j = sa[Rank[i] - 1];

s[i+k]==s[j+k]; k++);

}

bool check(int mid)

{

memset(vis, 0, sizeof(vis));

int cnt = 0;

for(int i = 1; i < n; i++)

{

if(height[i] < mid)

{

memset(vis, 0, sizeof(vis));

cnt = 0;

continue;

}

if(!vis[pos[sa[i]]])vis[pos[sa[i]]] = 1, cnt++;

if(!vis[pos[sa[i - 1]]])vis[pos[sa[i - 1]]] = 1, cnt++;

if(cnt == K)

{

for(int j = 0; j < mid; j++)

ans[j] = s[sa[i] + j] + 'a' - 1;

return 1;

}

return 0;

}

int main()

{

while(1)

{

K = read();

if(!K)break;

n = 0; m = 27;

char str[205];

for(int i = 1; i <= K; i++)

{

scanf("%s", str);

int l = strlen(str);

for(int j = 0; j < l; j++)

{

pos[n] = i;

s[n++] = str[j] - 'a' + 1;

}

pos[n] = i;

s[n++] = m++;

}

s[n++] = 0;

BuildSA();

BuildHeight();

int l = 0, r = 200, ansl = 0;

while(l <= r)

{

int mid = (l + r) >> 1;

if(check(mid))ansl = mid, l = mid + 1;

else r = mid - 1;

}

if(!ansl)

puts("IDENTITY LOST");

else

{

for(int i = 0; i < ansl; i++)

printf("%c", ans[i]);

cout << endl;

}

return 0;

}

hzwer.com _ Home | http://hzwer.com

分类目录

热门文章

Myfriends

近期评论