### 月份：2016年9月

HIHOCODER-WEEK117 二分图多重匹配

## HIHOCODER-WEEK117 二分图多重匹配

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DINIC
{
class Program
{
static void Main(string[] args)
{
while ((T--)>0)
{
string[] recv;
int n = Convert.ToInt32(recv[0]);
int m = Convert.ToInt32(recv[1]);
int[] M = new int[m];
int[,] f = new int[n + m + 3, n + m + 3];
for (int i = 0; i < m ; i++)
{
M[i] = Convert.ToInt32(recv[i]);
}
for (int i = 2; i <= n + 1; i++)
{
int a = Convert.ToInt32(recv[0]);
f[1, i] = a;
int b = Convert.ToInt32(recv[1]);
for (int j = 2; j < 2 + b; j++)
{
int bi = Convert.ToInt32(recv[j]);
f[i, bi + n + 1] = 1;
}
}
for (int i = n + 2; i <= n + 1 + m; i++)
{
f[i, n + m + 2] = M[i - n - 2];
}
DINIC d = new DINIC(n + m + 2, f);
bool flag = true;
for (int i = 0; i < m; i++)
{
if (f[n + i + 2, n + m + 2] == 0) continue;
else
{
flag = false;
break;
}
}
if (flag) Console.WriteLine("Yes");
else Console.WriteLine("No");
}
}
}

class DINIC
{
const int INF = 0x3f3f3f3f;
const int MAXN = 500;
const double pi = Math.PI;
int[,] flow = new int[MAXN, MAXN];
int[] dis;
int n, res;
public int ans;
public DINIC(int a, int[,] f)//a:arc count  b:point count f:squre
{
n = a;
flow = f;
ans = 0;
while (bfs() != 0)
{
while ((res=dfs(1, INF)) != 0) ans += res;
}
}
private void set(int[] a, int present)
{
for (int i=0;i<a.Length;i++)
{
a[i] = present;
}
}
private int bfs()
{
dis = new int[MAXN];
set(dis, -1);
dis[1] = 0;
Queue<int> q = new Queue<int>();
q.Enqueue(1);
while (q.Count != 0)
{
int k = q.Dequeue();
for (int i = 1; i <= n; i++)
{
if (flow[k, i] > 0 && dis[i] < 0)
{
dis[i] = dis[k] + 1;
q.Enqueue(i);
}
}
}
if (dis[n] > 0) return 1;
else return 0;
}
private int dfs(int x, int mx)
{
int a;
if (x == n) return mx;
for (int i = 1; i <= n; i++)
{

if ((flow[x, i] > 0) && (dis[i] == dis[x] + 1))
{
a = dfs(i, Math.Min(mx, flow[x, i]));
if (a!=0)
{
flow[x, i] -= a;
flow[i, x] += a;
return a;
}
}
}
return 0;
}
}
}

```

## 网络流最大流问题

DINIC算法的详细描述：https://en.wikipedia.org/wiki/Dinic%27s_algorithm

```    class DINIC
{
const int INF = 0x3f3f3f3f;
const int MAXN = 500;
int[,] flow = new int[MAXN, MAXN];
int[] dis;
int n, m, res;
public int ans { get; }
public DINIC(int a, int b, int[,] f)//a:arc count  b:point count f:squre
{
n = a;
m = b;
flow = f;
ans = 0;
while (bfs() != 0)
{
while ((res=dfs(1, INF)) != 0) ans += res;
}
}
private void set(int[] a, int present)
{
for (int i=0;i<a.Length;i++)
{
a[i] = present;
}
}
private int bfs()
{
dis = new int[MAXN];
set(dis, -1);
dis[1] = 0;
Queue<int> q = new Queue<int>();
q.Enqueue(1);
while (q.Count != 0)
{
int k = q.Dequeue();
for (int i = 1; i <= n; i++)
{
if (flow[k, i] > 0 && dis[i] < 0)
{
dis[i] = dis[k] + 1;
q.Enqueue(i);
}
}
}
if (dis[n] > 0) return 1;
else return 0;
}
private int dfs(int x, int mx)
{
int a;
if (x == n) return mx;
for (int i = 1; i <= n; i++)
{

if ((flow[x, i] > 0) && (dis[i] == dis[x] + 1))
{
a = dfs(i, Math.Min(mx, flow[x, i]));
if (a!=0)
{
flow[x, i] -= a;
flow[i, x] += a;
return a;
}
}
}
return 0;
}
}
```
[C#]TrieTree

## [C#]TrieTree

```using System;

namespace HIHOCODER1001
{
class TrieNode
{
private const int MAX = 26;
public bool isStr;
public int count;
public TrieNode[] next;
public TrieNode()
{
isStr = false;
count = 0;
next = new TrieNode[MAX];
}
}
class ReturnData
{
public int count;
public bool isfind;
public ReturnData()
{
count = 0;
isfind = false;
}
}
class OperateTrie
{
public OperateTrie()
{
}
public void Insert(string word)
{
{
Exception ex = new Exception("Empty string or node");
throw (ex);
}
while(word!="")
{
if (p.next[(int)(word[0]-'a')]==null)
{
TrieNode temp = new TrieNode();
temp.count = 1;
p.next[(int)(word[0] - 'a')] = temp;
p = p.next[(int)(word[0] - 'a')];
}
else
{
p = p.next[(int)(word[0] - 'a')];
p.count++;
}
word = word.Remove(0, 1);
}
p.isStr = true;
}
public ReturnData Search(string word)
{
ReturnData rd = new ReturnData();
int c = 0;
while (p != null && word != "")
{
if (p.next[(int)(word[0] - 'a')] != null)
c = p.next[(int)(word[0] - 'a')].count;
else c = 0;
p = p.next[(int)(word[0] - 'a')];
word = word.Remove(0, 1);
}
if (p != null && p.isStr == true) rd.isfind = true;
rd.count = c;
return rd;
}
}
class Program
{
static void Main(string[] args)
{
OperateTrie ot = new OperateTrie();
for (int i = 0; i < n; i++)
{
ot.Insert(s);
}
for (int i = 0; i < m; i++)
{
int c = ot.Search(s).count;
Console.WriteLine(c);
}
ot = null;
}
}
}

```
REPORT POJ1258-Agri-Net

## REPORT POJ1258-Agri-Net

Agri-Net
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 53017 Accepted: 22052
Description

Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.
Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms.
Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm.
The distance between any two farms will not exceed 100,000.

//=======================================================

//=======================================================

```#include <iostream>
#include <string.h>
#define inf 0x3f3f3f3f
#define N 110
using namespace std;
int G[N][N], n;

int prim()
{
int dist[N], visited[N];
int pos, min = inf, result = 0;
memset(visited, 0, sizeof(visited));
visited[1] = 1; pos = 1;
for (int i = 1; i <= n; i++)
if (i != pos) dist[i] = G[pos][i];
for (int i = 1; i<n; i++)
{
min = inf;
for (int j = 1; j <= n; j++)
if (visited[j] == 0 && min > dist[j])
min = dist[j], pos = j;
result += min;
visited[pos] = 1;
for (int j = 1; j <= n; j++)
if (visited[j] == 0 && dist[j]>G[pos][j])
dist[j] = G[pos][j];
}
return result;
}

int main()
{
while (cin >> n)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> G[i][j];
cout << prim() << endl;
}
return 0;
}
```

## 简单文字分割V1

`using AForge.Imaging.Filters;`

```        public static List<Bitmap> filter(Bitmap segb)
{
var list = new List<Bitmap>();
int[] rows = new int[segb.Height];
for (int y = 0; y < segb.Height; y++)
{
for (int x = 0; x < segb.Width; x++)
{
var pixel = segb.GetPixel(x, y);
if (pixel.R == 0) rows[y] = ++rows[y];
}
}
int bottom = 0, top = 0;
for (int y = 0; y < rows.Length; y++)
{
if (rows[y] > 0 || (y + 1 < rows.Length && rows[y + 1] > 0))
{
if (top == 0) top = y;
else bottom = y;
}
else
{
if ((top > 0 || bottom > 0) && bottom - top > 0)
{
Crop corp = new Crop(new Rectangle(0, top, segb.Width, bottom - top + 1));
var small = corp.Apply(segb);
}
top = bottom = 0;
}
}

var corplist = new List<Bitmap>();
foreach (var b in list)
{
int[] cols = new int[b.Width];
for (int x = 0; x < b.Width; x++)
{
for (int y = 0; y < b.Height; y++)
{
var pixel = b.GetPixel(x, y);
if (pixel.R == 0) cols[x] = ++cols[x];
}
}
int left = 0, right = 0;
for (int i = 0; i < cols.Length; i++)
{
if (cols[i] > 0 || (i + 1 < cols.Length && cols[i + 1] > 0))
{
if (left == 0) left = i;
else right = i;

}
else
{
if ((left > 0 || right > 0))
{
Crop corp = new Crop(new Rectangle(left, 0, right - left + 1, b.Height));
var small = corp.Apply(b);
}

left = right = 0;
}
}
}
return corplist;
}
```
REPORT POJ2485-Highways

## REPORT POJ2485-Highways

Highways
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 28843 Accepted: 13165
Description

The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem. They’re planning to build some highways so that it will be possible to drive between any pair of towns without leaving the highway system.

Flatopian towns are numbered from 1 to N. Each highway connects exactly two towns. All highways follow straight lines. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways.

The Flatopian government wants to minimize the length of the longest highway to be built. However, they want to guarantee that every town is highway-reachable from every other town.
//===================================================
PRIM求最小生成树，求的时候记录当前最小生成树里的最大边

//===================================================

```#include <iostream>
#include <cstdio>
#include <string.h>
#define inf 0x3f3f3f3f
#define MAXN 505
using namespace std;

int dist[MAXN][MAXN];
int n;

int prim()
{
int s = 1, m = 1, min, point, ANS = 0, currentShortest[MAXN];
bool u[501] = { false };
u[s] = true;

memset(currentShortest, inf, sizeof(currentShortest));

while (true)
{
if (m == n)
break;

min = inf;
for (int i = 2; i <= n; i++)
{
if (!u[i] && currentShortest[i] > dist[s][i]) currentShortest[i] = dist[s][i];
if (!u[i] && min>currentShortest[i])
{
min = currentShortest[i];
point = i;

}
}

if (ANS < min) ANS = min;
s = point;
u[s] = true;
m++;
}
return ANS;
}

int main()
{
int T;
cin >> T;
while (T--)
{
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%d",&dist[i][j]);
cout << prim() << endl;
}
return 0;
}
```

## 祝我20岁生日快乐

20岁了。

REPORT POJ1789-Truck History

## REPORT POJ1789-Truck History

Truck History
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 25362 Accepted: 9902
Description

Advanced Cargo Movement, Ltd. uses trucks of different types. Some trucks are used for vegetable delivery, other for furniture, or for bricks. The company has its own code describing each type of a truck. The code is simply a string of exactly seven lowercase letters (each letter on each position has a very special meaning but that is unimportant for this task). At the beginning of company’s history, just a single truck type was used but later other types were derived from it, then from the new types another types were derived, and so on.

Today, ACM is rich enough to pay historians to study its history. One thing historians tried to find out is so called derivation plan — i.e. how the truck types were derived. They defined the distance of truck types as the number of positions with different letters in truck type codes. They also assumed that each truck type was derived from exactly one other truck type (except for the first truck type which was not derived from any other type). The quality of a derivation plan was then defined as
1/Σ(to,td)d(to,td)

where the sum goes over all pairs of types in the derivation plan such that to is the original type and td the type derived from it and d(to,td) is the distance of the types.
Since historians failed, you are to write a program to help them. Given the codes of truck types, your program should find the highest possible quality of a derivation plan.

//=========================================================

//=========================================================

```#include <iostream>
#include <string>
#define INF 0x3f3f3f3f
#define MAX 2005
using namespace std;

int N;
string t[MAX];
int d[MAX][MAX];

int calc(int a, int b)
{
int d = 0;
for (int i = 0; i < 7; i++)
if (t[a][i] != t[b][i]) d++;
return d;
}

int prim(void)
{
int startPoint = 1, visitedCount = 1, weight = 0, shortest, flag, shortestDist[MAX];
bool includePoint[MAX];

memset(shortestDist, INF, sizeof(shortestDist));
memset(includePoint, false, sizeof(includePoint));
includePoint[startPoint] = true;

while (true)
{
if (visitedCount == N) break;
shortest = INF;
for (int j = 2; j <= N; j++)
{
if (!includePoint[j] && shortestDist[j] > d[startPoint][j])
shortestDist[j] = d[startPoint][j];
if (!includePoint[j] && shortest > shortestDist[j])
{
shortest = shortestDist[j];
flag = j;
}
}
startPoint = flag;
includePoint[startPoint] = true;
weight += shortest;
visitedCount++;
}
return weight;
}

int main()
{
while (cin >> N && N != 0)
{
for (int i = 1; i <= N; i++)
cin >> t[i];
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
{
d[i][j] = calc(i, j);
}
int ans = prim();
cout << "The highest possible quality is 1/" << ans << '.' << endl;
}
}
```
REPORT HDU5873-Football Games

## REPORT HDU5873-Football Games

Football Games

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 466 Accepted Submission(s): 171

Problem Description
A mysterious country will hold a football world championships—Abnormal Cup, attracting football teams and fans from all around the world. This country is so mysterious that none of the information of the games will be open to the public till the end of all the matches. And finally only the score of each team will be announced.

At the first phase of the championships, teams are divided into M groups using the single round robin rule where one and only one game will be played between each pair of teams within each group. The winner of a game scores 2 points, the loser scores 0, when the game is tied both score 1 point. The schedule of these games are unknown, only the scores of each team in each group are available.

When those games finished, some insider revealed that there were some false scores in some groups. This has aroused great concern among the pubic, so the the Association of Credit Management (ACM) asks you to judge which groups’ scores must be false.

Multiple test cases, process till end of the input.

//=======================================================

WA了三次因为没看到输入的第一句话。

MDZZ
//=======================================================

```#include <iostream>
using namespace std;

int main()
{
int T;
while (cin >> T)
{
while (T--)
{
int m, s, tots = 0, s1 = 0, s0 = 0;
bool flag = false;
cin >> m;
for (int i = 0; i < m; i++)
{
cin >> s;
if (s % 2 == 1) s1++;
tots += s;
if (s == 0) s0++;
if (s > 2 * m - 2)
{
flag = true;
}
}
if ((m*(m - 1) == tots) && (s1 % 2 == 0) && (s0 <= 1) && !flag)
cout << "T" << endl;
else cout << "F" << endl;
}
}
return 0;
}
```
REPORT HDU5876-Sparse Graph

## REPORT HDU5876-Sparse Graph

Sparse Graph

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 403 Accepted Submission(s): 133

Problem Description
In graph theory, the complement of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G.

Now you are given an undirected graph G of N nodes and M bidirectional edges of unit length. Consider the complement of G, i.e., H. For a given vertex S on H, you are required to compute the shortest distances from S to all N−1 other vertices.

Input
There are multiple test cases. The first line of input is an integer T(1≤T<35) denoting the number of test cases. For each test case, the first line contains two integers N(2≤N≤200000) and M(0≤M≤20000). The following M lines each contains two distinct integers u,v(1≤u,v≤N) denoting an edge. And S (1≤S≤N) is given on the last line. Output For each of T test cases, print a single line consisting of N−1 space separated integers, denoting shortest distances of the remaining N−1 vertices from S (if a vertex cannot be reached from S, output ``-1" (without quotes) instead) in ascending order of vertex number. Sample Input 1 2 0 1 Sample Output 1 Source 2016 ACM/ICPC Asia Regional Dalian Online //======================================================= 比赛的时候以为是最短路，就开始求补然后突然发现邻接表邻接矩阵好像都没法存补图…… 我居然没从另一个侧面去想一下…… MDZZ…… 比完赛看完题解才知道原来BFS就好了…… //======================================================= 感谢dalao的题解
//=======================================================

```#include <iostream>
#include <set>
#include <queue>
#define MAXN 200020
#define MAXM 50005
#define INF  0x3F3F3F3F
using namespace std;

int n, m, edges, g[MAXN], nxt[MAXM], v[MAXM], S, d[MAXN];

void BFS()
{
set<int> a, b;
set<int>::iterator it;
queue<int> Q;
for (int i = 1; i <= n; i++) d[i] = INF;
d[S] = 0;
Q.push(S);
for (int i = 1; i <= n; i++)
if (i != S) a.insert(i);
while (!Q.empty())
{
int now;
now = Q.front();
Q.pop();
for (int i = g[now]; i; i = nxt[i])
if (a.find(v[i]) != a.end())
{
a.erase(v[i]);
b.insert(v[i]);
}
for (it = a.begin(); it != a.end(); it++)
{
Q.push(*it);
d[*it] = d[now] + 1;
}
a.swap(b);
b.clear();
}
for (int i = 1; i < n; i++)
{
if (i != S) cout << (d[i] == INF ? -1 : d[i]) << ' ';
}
cout << d[n];
cout << endl;
}

int main()
{
int T; cin >> T;
while (T--)
{
edges = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++) g[i] = 0;
for (int i = 1; i <= m; i++)
{
int U, V;
cin >> U >> V;
v[++edges] = V, nxt[edges] = g[U], g[U] = edges;
v[++edges] = U, nxt[edges] = g[V], g[V] = edges;
}
cin >> S;
BFS();
}
return 0;
}
```