下雪了

洛谷P3386 【模板】二分图匹配

二分图匈牙利算法,归根结底就是递归找新边找找找!

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<deque>
#include<list>
#include<map>
#define int long long
#define ffor(i, a, b) for(ll i = a; i <= b; i++)
#define rfor(i, a, b) for(ll i = a; i >= b; i--)
#define mes(a,b) memset(a, b, sizeof(a))
#define cos(x) cos(x*PI/180.0)
#define sin(x) sin(x*PI/180.0)
#define stop system("pause")
#define see(s,x) cout<<(s)<<'='<<(x)<<endl
#define IMAX 0x7fffffff
#define PI 3.141592654
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x&(-x))
#define test(x) cout<<"Test "<<(x)<<endl;
typedef long long ll;
ll mod;
ll max(ll a, ll b) { return(a > b) ? a : b; }
ll min(ll a, ll b) { return(a < b) ? a : b; }
using namespace std;

vector<int> G[1005];
int tab[1005];
bool v[1005];

bool deal(int x)
{
    for (int i : G[x])
    {
        if (!v[i])
        {
            v[i] = true;
            if (!tab[i] || deal(tab[i]))
            {
                tab[i] = x;
                return true;
            }
        }
    }
    return false;
}

signed main()
{
    mes(tab, 0);
    int n, m, e;
    cin >> n >> m >> e;
    ffor(i, 1, e)
    {
        int x, y;
        scanf("%lld%lld", &x, &y);
        if (x <= n && y <= m)
            G[x].push_back(y);
    }
    int res = 0;
    ffor(i, 1, n)
    {
        mes(v, 0);
        res += deal(i);
    }
    cout << res << endl;
}

洛谷 P3381 最小费用最大流(网络流/最小费用最大流/Dinic + SFPA)

如题,给出一个网络图,以及其源点和汇点,每条边已知其最大流量和单位流量费用,求出其网络最大流和在最大流情况下的最小费用。

输入格式

第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来M行每行包含四个正整数ui、vi、wi、fi,表示第i条有向边从ui出发,到达vi,边权为wi(即该边最大流量为wi),单位流量的费用为fi。

输出格式

一行,包含两个整数,依次为最大流量和在最大流量情况下的最小费用。

输入输出样例

输入 #1

4 5 4 3
4 2 30 2
4 3 20 3
2 3 20 1
2 1 30 9
1 3 40 5

输出 #1

50 280

说明/提示

时空限制:1000ms,128M

(BYX:最后两个点改成了1200ms)

数据规模:

对于30%的数据:N<=10,M<=10

对于70%的数据:N<=1000,M<=1000

对于100%的数据:N<=5000,M<=50000

样例说明:

如图,最优方案如下:

第一条流为4–>3,流量为20,费用为3*20=60。

第二条流为4–>2–>3,流量为20,费用为(2+1)*20=60。

第三条流为4–>2–>1–>3,流量为10,费用为(2+9+5)*10=160。

故最大流量为50,在此状况下最小费用为60+60+160=280。

故输出50 280。

思路:初学费用流,找到了一篇不错的教程,思路是利用最短路保证最小费用,再在最大流的基础上,算出最大流的最小的费用,似乎可以把sfpa换成dijkstra?

AC代码:

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<deque>
#include<list>
#include<map>
#define int long long
#define ffor(i, a, b) for(ll i = a; i <= b; i++)
#define rfor(i, a, b) for(ll i = a; i >= b; i--)
#define mes(a,b) memset(a, b, sizeof(a))
#define cos(x) cos(x*PI/180.0)
#define sin(x) sin(x*PI/180.0)
#define stop system("pause")
#define see(s,x) cout<<(s)<<'='<<(x)<<endl
#define IMAX 0x7fffffff
#define PI 3.141592654
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x&(-x))
#define test(x) cout<<"Test "<<(x)<<endl;
typedef long long ll;
ll mod;
ll max(ll a, ll b) { return(a > b) ? a : b; }
ll min(ll a, ll b) { return(a < b) ? a : b; }
using namespace std;

struct unit
{
    int to;//指向
    int f;//流量
    int w;//单位花费
    int rev;//反向边序号
    unit() {};
    unit(int n, int ff, int ww, int r) :to(n), f(ff), w(ww), rev(r) {};
};
vector<unit> G[50001];
int cur[50001];
int dis[50001];
bool v[50001];

int n, m, st, ed;
int maxflow, mincost;

void add(int x, int y, int f, int w)//建边
{
    G[x].push_back(unit(y, f, w, G[y].size()));
    G[y].push_back(unit(x, 0, -w, G[x].size() - 1));//反向边,流量为0,单位花费为负
}

bool spfa()//标准SPFA
{
    ffor(i, 1, n)
    {
        v[i] = false;
        dis[i] = IMAX;
    }
    dis[st] = 0;
    queue<int> q;
    q.push(st);
    while (!q.empty())
    {
        int f = q.front();
        q.pop();
        v[f] = false;
        for (vector<unit>::iterator it = G[f].begin(); it != G[f].end(); it++)
        {
            unit u = *it;
            if (u.f && dis[f] + u.w < dis[u.to])
            {
                dis[u.to] = dis[f] + u.w;
                if (!v[u.to])
                {
                    q.push(u.to);
                    v[u.to] = true;
                }
            }
        }
    }
    return dis[ed] != IMAX;//能走到就返回
}

int dfs(int x, int f)
{
    if (x == ed)
        return f;
    v[x] = true;//防止重复走
    int sum = 0;
    for (int& i = cur[x]; i <= G[x].size() - 1; i++)
    {
        unit& u = G[x][i];
        if (!v[u.to] && u.f && dis[u.to] == dis[x] + u.w)
        {
            int flow = dfs(u.to, min(f - sum, u.f));
            if (flow)//确认可以流通,就对边进行操作,记录最大流和最小花费
            {
                sum += flow;
                u.f -= flow;
                G[u.to][u.rev].f += flow;
                mincost += u.w * flow;
                if (sum == f)break;
            }
        }
    }
    v[x] = false;
    return sum;
}
void dinic()
{
    while (spfa())
    {
        mes(cur, 0);
        maxflow += dfs(st, IMAX);
    }
}

signed main()
{
    cin >> n >> m >> st >> ed;
    maxflow = mincost = 0;
    ffor(i, 1, m)
    {
        int x, y, w, c;
        scanf("%lld%lld%lld%lld", &x, &y, &w, &c);
        add(x, y, w, c);
    }
    dinic();
    printf("%lld %lld\n", maxflow, mincost);
}

 

【数据库的创建】万恶的数据表……

因为实验报告和数据文件严重不符,只能手动修改了,这里记录一下…..
create table employee
(
employeeNo char(8) primary key,
employeename varchar(8),
sex char(1),
birthday datetime,
address varchar(50),
telephone varchar(20),
hiredate datetime,
department varchar(30),
headship varchar(6),
salary numeric(8,2)
);

create table customer
(
customerNo char(9) primary key,
customername varchar(40),
telephone varchar(20),
address varchar(40),
zip char(6)
);

create table product
(
productNo char(9) primary key,
productName varchar(40),
productClass varchar(20),
productPrice numeric(8,2)
);

create table orderMaster
(
orderNo char(12) primary key,
customerNo char(9),
foreign key (customerNo) references customer(customerNo),
saleNo char(8),
orderdate datetime,
orderSum numeric(8,2),
invoiceNo char(10)
);

create table orderDetail
(
orderNo char(12),
productNo char(9),
quantity int,
price int,
primary key (orderNo,productNo),
foreign key (orderNo) references orderMaster(orderNo),
foreign key (productNo) references product(productNo)
);

【心理学】【摘自百度百科】人际交往距离

         人与人之间需要保持一定的空间距离。任何一个人,都需要在自己的周围有一个自己把握的自我空间,它就像一个无形的”气泡”一样为自己”割据”了一定的”领域”。而当这个自我空间被人触犯就会感到不舒服,不安全,甚至恼怒起来。
        一位心理学家做过这样一个实验。在一个刚刚开门的大阅览室里,当里面只有一位读者时,心理学家就进去拿椅子坐在他或她的旁边。试验进行了整整80个人次。结果证明,在一个只有两位读者的空旷的阅览室里,没有一个被试者能够忍受一个陌生人紧挨自己坐下。就一般而言,交往双方的人际关系以及所处情境决定着相互间自我空间的范围。美国人类学家爱德华·霍尔博士划分了四种区域或距离,各种距离都与对方的关系相称。
        公众距离(Public Distance),其近范围为12~25英尺(约3.7~7.6米),远范围在25英尺之外,一般适用于演讲者与听众、彼此极为生硬的交谈及非正式的场合。在商务活动中,根据其活动的对象和目的,选择和保持合适的距离是极为重要的。这是一个几乎能容纳一切人的”门户开放”的空间,人们完全可以对处于空间的其他人,”视而不见”,不予交往,因为相互之间未必发生一定联系。因此,这个空间的交往,大多是当众演讲之类,当演讲者试图与一个特定的听众谈话时,他必须走下讲台,使两个人的距离缩短为个人距离或社交距离,才能够实现有效沟通。
        社交距离(Social Distance),大概是120~370cm,就像隔一张办公桌那样。一般工作场合人们多采用这种距离交谈,在小型招待会上,与没有过多交往的人打招呼可采用此距离,是体现出一种社交性或礼节上的较正式关系。其近范围为4~7英尺(1.2~2.1米),一般在工作环境和社交聚会上,人们都保持这种程度的距离。一次,一个外交会谈座位的安排出现了疏忽,在两个并列的单人沙发中间没有放增加距离的茶几。结果,客人自始至终都尽量靠到沙发外侧扶手上,且身体也不得不常常后仰。可见,不同的情境、不同的关系需要有不同的人际距离。距离与情境和关系不相对应,会明显导致人出现心理不适感。 社交距离的远范围为7~12英尺(2.1~3.7米),表现为一种更加正式的交往关系。公司的经理们常用一个大而宽阔的办公桌,并将来访者的座位放在离桌子一段距离的地方,这样与来访者谈话时就能保持一定的距离。如企业或国家领导人之间的谈判,工作招聘时的面谈,教授和大学生的论文答辩等等,往往都要隔一张桌子或保持一定距离,这样就增加了一种庄重的气氛。 在社交距离范围内,已经没有直接的身体接触,说话时,也要适当提高声音,需要更充分的目光接触。如果谈话者得不到对方目光的支持,他(或她)会有强烈的被忽视、被拒绝的感受。这时,相互间的目光接触已是交谈中不可缺免的感情交流形式了。
        个人距离(Personal Distance),大概从45cm~120cm,就像伸手碰到对方那样,虽然认识,但是没有特别的关系。这是在进行非正式的个人交谈时最经常保持的距离。和人谈话时,不可站得太近,一般保持在50cm以外为宜。这是人际间隔上稍有分寸感的距离,已较少直接的身体接触。个人距离的近范围为1.5~2.5英尺(46~76厘米)之间,正好能相互亲切握手,友好交谈。这是与熟人交往的空间。陌生人进入这个距离会构成对别人的侵犯。个人距离的远范围是2.5~4英尺(76~122厘米)。任何朋友和熟人都可以自由地进入这个空间,不过,在通常情况下,较为融洽的熟人之间交往时保持的距离更靠近远范围的近距离(2.5英尺)一端,而陌生人之间谈话则更靠近远范围的远距离(4英尺)端。

       亲密距离(Intimate Distance)是人际交往中的最小间隔或几无间隔,即我们常说的”亲密无间”,其近范围在6英寸(约15厘米)之内,彼此间可能肌肤相触,耳鬓厮磨,以至相互能感受到对方的体温、气味和气息。其远范围是6英寸到18英寸(15厘米~44厘米)之间,身体上的接触可能表现为挽臂执手,或促膝谈心,仍体现出亲密友好的人际关系。一般是亲人、很熟的朋友、情侣和夫妻才会出现这种情况。

就交往情境而言,亲密距离属于私下情境,只限于在情感上联系高度密切的人之间使用,在社交场合,大庭广众之前,两个人(尤其是异性)如此贴近,就不太雅观。在同性别的人之间,往往只限于贴心朋友,彼此十分熟识而随和,可以不拘小节,无话不谈。在异性之间,只限于夫妻和恋人之间。因此,在人际交往中,一个不属于这个亲密距离圈子内的人随意闯入这一空间,不管他的用心如何,都是不礼貌的,会引起对方的反感,也会自讨没趣。当无权进入亲密距离的人闯入这个范围时,会令人不安。在拥挤的公共汽车、地铁和电梯上,由于人员的拥挤,亲密距离常常遭到侵犯。于是,人们尽可能地在心理上保护自己的空间距离。在西方,当你在电梯或者公共交通工具里碰到拥挤的局面时,有一些不成文的规则是必须遵守的:你不能同任何人说话,即使是你认识的人;你的眼神必须始终避免同他人眼神的接触;面部不能有任何表情;人越拥挤,你的身体越不能随意动弹;在电梯里,你必须看着头上的楼层号码等。
        人际交往的空间距离不是固定不变的,它具有一定的伸缩性,这依赖于具体情境、交谈双方的关系、社会地位、文化背景、性格特征、心境等。人际交往中,亲密距离与个人距离通常都是在非正式社交情境中使用,在正式社交场合则使用社交距离。社会地位不同,交往的自我空间距离也有差异。一般说来,有权力有地位的人对于个人空间的需求相应会大一些。此外,人们对自我空间需要也会随具体情境的变化而变化。例如,在拥挤的公共汽车上,人们无法考虑自我空间。若在较为空旷的公共场合,人们的空间距离就会扩大,如公园休息亭和较空的餐馆,别人毫无理由挨着自己坐下,就会引起怀疑和不自然的感觉。我们了解了交往中人们所需的自我空间及适当的交往距离,就能有意识地选择与人交往的最佳距离,而且,通过空间距离的信息,还可以很好地了解一个人的实际社会地位、性格以及人们之间的相互关系,更好地进行人际交往。