月份:2016年9月

HIHOCODER-WEEK117 二分图多重匹配

HIHOCODER-WEEK117 二分图多重匹配

题目链接:http://hihocoder.com/contest/hiho117/problem/1
我觉得题目里面的关于二分图多重匹配的题解讲得相当透彻,构图之后直接DINIC就可以了。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DINIC
{
    class Program
    {
        static void Main(string[] args)
        {
            int T = Convert.ToInt32(Console.ReadLine());
            while ((T--)>0)
            {
                string[] recv;
                recv = Console.ReadLine().Trim().Split();
                int n = Convert.ToInt32(recv[0]);
                int m = Convert.ToInt32(recv[1]);
                recv = Console.ReadLine().Trim().Split();
                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++)
                {
                    recv = Console.ReadLine().Trim().Split();
                    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;
        }
    }
}

网络流最大流问题

网络流最大流问题

先说两个定理:
最大流定理:如果残留网络上找不到增广路径,则当前流为最大流。如果当前流不为最大流,则一定有增广路径。
最大流最小割定理:任何网络中最大流的流量等于最小割的容量。

残留网络是指对于网络流上每条流的权C(u,v)的值更新为C(u,v)-P(u,v),并且添加反向弧C(v,u),C(v,u)构成的网络流即为残留网络。

DINIC算法的详细描述:https://en.wikipedia.org/wiki/Dinic%27s_algorithm
大致就是:
根据残留网络计算层次图
在层次图中使用DFS进行增广直到不存在增广路
重复以上步骤直到无法增广

一个鶸的代码

    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

简单trie树的csharp实现,包含插入,查找和统计三个主要功能
至少A了HIHOCODER的1014

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
    {
        private TrieNode head;
        public OperateTrie()
        {
            head = new TrieNode();
        }
        public void Insert(string word)
        {
            if (head==null||word=="")
            {
                Exception ex = new Exception("Empty string or node");
                throw (ex);
            }
            TrieNode p = head;
            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();
            TrieNode p = head;
            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();
            int n = Convert.ToInt32(Console.ReadLine());
            for (int i = 0; i < n; i++)
            {
                string s = Console.ReadLine();
                ot.Insert(s);
            }
            int m = Convert.ToInt32(Console.ReadLine());
            for (int i = 0; i < m; i++)
            {
                string s = Console.ReadLine();
                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.

//=======================================================
赤裸裸的最小生成树,在于使用PRIM还是KRUSKAL
向PRIM势力低头(滑稽
注意输入输出
//=======================================================

#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

简单文字分割V1

已知BUG:当字体中某些左右结构的字和标点符号有中间缝隙时会导致切成两块,速度慢
记得要

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);
                        list.Add(small);
                    }
                    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);
                            corplist.Add(small);
                        }

                        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求最小生成树,求的时候记录当前最小生成树里的最大边
还有记得用scanf……用cin就TLE
//===================================================

#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岁生日快乐

20岁了。
感觉这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.

//=========================================================
如果没有题解我应该做不出……完全没看懂……有毒……先感谢http://blog.csdn.net/lyy289065406/article/details/6645974
主要是PRIM算法,由距离构图然后用这个图构筑最小生成树。
所以题目的关键是构图
//=========================================================

#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了三次因为没看到输入的第一句话。
这题……怎么说呢
所有球队总分等于m*(m-1),然后因为最多只有一个0分,一个队的最大得分是m*2-2,奇数分队伍是偶数支。
我最开始还在想是不是要枚举……
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;
}